Chapter $2$ Languages

$1.$ Using induction on i$,$ prove that $()=($

$)$ for any string w and all i $^30.$

Hints: feel free to use the following Theorem in your proof

Let $,$ in $\backslash$Sigma $,$ then $()-=--.$

For the following exercises, give a regular expression that represents that described set.

$2.$ The set of strings over $\{$a$,$ b$,$ c$\}$ in which all the a$$s precede the b$$s$,$ which in turn

precede the c$$s$.$ It is possible that there are no a$$s$,$ b$$s$,$ or c$$s$.$

$3.$ The same as Exercise $2$ without the null string.

$4.$ The set of strings over $\{$a$,$ b$\}$ that contain the substring aa and the substring bb