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 one$)$

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

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

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

$Y=\{\begin{array}{c}{0}^n|n\end{array}$ is a prime