Exercise $1($Ex$.22,$ Chapter $2$ of $[$Martin; $2011]).$ Using the pumping lemma, show that

the languages below is not regular:

$L=\{a^{n}b{a}^{2n}|n0\}$

Exercise $2($Ex$.12,$ Chapter $2$ of $[$Martin; $2011]).$ For the following languages in

exercises in c$,$ d$,$ and e$,$ draw an FA for accepting it$.$

c$.\{a,b{\}}^{*}\{b,aa\}\{a,b{\}}^{*}$

d$.\{bbb,$baa${\}}^{*}\{a\}$

Exercise $3($Ex$.41,$ Chapter $3$ of $[$Martin; $2011]).$ For each of the following regular

expressions, draw an NFA accepting the corresponding language, so that there is a

recognizable correspondence between the regular expression and the transition diagram.

b$.(a+b{)}^{*}(abb+$ababa$)(a+b{)}^{*}$

e$.(a^{*}bb{)}^{*}+b{b}^{*}{a}^{*}$

Exercise $4($Ex$.2,$ Chapter $6$ of $[$Martin; $2011]).$ In each case below, show using the

pumping lemma that the given language is not a CFL$.$

a$.\{\begin{array}{c}{a}^i{b}^j{c}^k|ij\end{array}$ or $ik.$

Exercise $5($Ex$.4,$ Chapter $7$ of $[$Martin; $2011]).$ For the following language, show a

transition diagram for a Turing machine that accepts that language.

d$.\{a^i{b}^j|ij\}.$