Q$1.(3$ points$).$ Consider the following NFA $M$ over the alphabet $=\{0,1\}$ :

Give a regular expression for the language $L$ recognized by $M.$ Use the

following order in ripping $($removing$)$ out states: $q_1,q_2,q_3,q_4,q_5,q_0.$

Q$2.(2$ points$).$ For any string $w=w_1{w}_{2}cdots{w}_n,$ the reverse of $w,$ written

$w^R,$ is the string $w$ in reverse order, $w_{n}cdots{w}_2{w}_1.$ For any language $A,$ let

$A^R=\{w^R|winA\}.$ For the language $L$ recognized by the machine $M$ in Q$1,$

give an NFA $M^{\text{'}}$ to recognize $L^R.$

Q$3.(3$ points$).$ Convert the following regular expressions to nondeterministic

finite automata:

$($i$)0^{**}10(01{)}^{+}10$

$($ii$)(({100}^{**}{)}^{**}10{)}^{**}{10}^{**}$

Q$4.(2$ points$).$ Use the pumping lemma to show that the language

$\{(00{)}^n{1}^m(00{)}^n|m,n0\}$ is not regular.