How many substrings aab are in wwR

w$,$ where w $=$ aabbab?

$2.$ Use induction on n to show that $|$un

$|=$ n $|$u$|$ for all strings u and

all n$.$

$3.$ The reverse of a string, introduced informally above, can be

defined more precisely by the recursive rules

a R $=$

a$,$

$($

wa$)$

R $=$

aw R $,$

for all a in $\backslash$Sigma $,$ w in $\backslash$Sigma $*.$ Use this to prove that

$($

uv$)$

R $=$

v R u R $,$

for all u$,$ v in $\backslash$Sigma $+$

$.$

$4.$ Prove that $($w R $)$ R

$=$ w for all w in $\backslash$Sigma $*.$

$5.$ Let L $=\{$ab$,$ aa$,$ baa$\}.$ Which of the following strings are in L$*$:

abaabaaabaa, aaaabaaaa, baaaaabaaaab, baaaaabaa? Which strings

are in L$4$

$?$

$6.$ Let $\backslash$Sigma $=\{$a$,$ b$\}$ and L $=\{$aa$,$ bb$\}.$ Use set notation to describe L$.$

$7.$ Let L be any language on a nonempty alphabet. Show that L and

L cannot both be finite.

$8.$ Are there languages for which L $*=($L$)*$

$?$

$9.$ Prove that

$($L $1$ L $2)$ R $=$ L R

$2$ L R

$1$

for all languages L$1$ and L$2.$

$10.$ Show that $($L$*)*=$ L$*$ for all languages.

$11.$ Prove or disprove the following claims.

$($a$)($L $1\backslash$cup L $2)$ R $=$ L R

$1\backslash$cup L R

$2$ for all languages L$1$ and L$2.$

$($b$)($L R $)*$

$=($L$*)$ R for all languages L$.$

$12.$ Find a grammar for the language L $=\{$an

$,$ where n is even$\}.$

$13.$ Find a grammar for the language L $=\{$an

$,$ where n is even and n $>$

$3\}.$

$14.$ Find grammars for $\backslash$Sigma $=\{$a$,$ b$\}$ that generate the sets of

$($a$)$ all strings with exactly two a$$s$.$

$($b$)$ all strings with at least two a$$s$.$

$($c$)$ all strings with no more than three a$$s$.$

$($d$)$ all strings with at least three a$$s$.$

$($e$)$ all strings that start with a and end with b$.$

$($f$)$ all strings with an even number of b$$s$.$

In each case, give convincing arguments that the grammar you

give does indeed generate the indicated lang