Problem $2$

Total: $20$ points $(10$ points each$)$

Convert the following NFAs into equivalent regular expressions. Show all the Intermediate steps

GNFAs$)$ and znake appropriate comments to help graders understand your steps.

For example, step $1$: remove state $"{}_0"$; step $2$: remove state $"q_3",$ etc.

Convert the NFA in Figure $1$ into an equivalent regular

Problem $3$

Total: $20$ points $(10$ points each$)$

Alphabet $=\{0,1\}$

For each provided language $(x$ and $Y),$ please answer these two questions:

$($a$)$ Is the language regular or non$-$regular?

$($b$)$ If your answer is regular, please provide either a DFA, NFA or regular expression $($choose only

that recognizes the language. If your answer is non$-$regular, please prove it by contradiction using Pump

Lemma. The presentation format of the proof is expected to follow those examples in the book.

$x=\{0^m{1}^n|m>n0\}$

$|)$:$\}$ is a prime expression.

Figure $1$: