Note: The a$$s and b$$s can be in any order. Your regular expression should handle this.

b$.$ L$2=\{$ w in $\{0,1\}*$: w is the binary representation of a prime number between $2$ and $15.\}$ Justify your answer.

c$.$ L$3=\{$ anbm: n m Justify your answer.

Problem $8$ Let $\backslash$Sigma $=\{$a$,$b$\}.$

a$.$ Prove that r$=$a$($a$+$b$)^(*)$a$+$b$($a$+$b$)^(*)$b is a regular expression using the inductive

definition of regular expressions. Use the techniques on slide $9$ in Chap$3\mathrm{.}1$ power point.

b$.$ Give a simple English description of the strings in L$($r$).$

c$.$ Create an NFA M such that L$($r$)=$L$($M$).$ Create and test your NFA on Jflap. Submit the

jflap diagram for M and the testing diagram for M $.$

d$.$ Testcases: aa$,$ bb$,$ aabb, abbaba, bbaaab, a$,$ b$,$ ababbb, baaababa

Problem $7($Concatenation Problem$)$

Let L$\_(1)=\{$win$\{$a$,$b$\}^(*)$:n$\_($a$)($w$)>=3,$n$\_($a$)($w$)$mod$3=0\}.$

Let L$\_(2)=\{$b$($ab$)^($n$)$:n$>=0\}.$

Let L$=$L$\_(1)$L$\_(2).$

aM$\_(1)$ that accepts L$\_(1).$ Create and test your M$\_(1)$ on JFLAP. Copy the M$\_(1)$

diagram into Homework #$3.$ Make up good testcases.

bM$\_(2)$ that accepts L$\_(2).$ Create and test M$\_(2)$ on JFLAP. Copy the M$\_(2)$ diagram

into Homework #$3.$ Make up good test cases.

cL$=$L$\_(1)$L$\_(2).$ Create and test M on JFLAP. Copy the NFA

diagram into Homework #$3.$

Required: M is a machine that concatenates L$\_(1)$ and L$\_(2).$ Use the method from the Chap

$2\mathrm{.}2$ slides. You must use a $\backslash$lambda transition to jump from L$\_(1)$ to L$\_(2).$

d