I.

Describe the languages generated by:

a$.S$ASA$|A|$

$A00|||$

b$.S0S1|SS|$

c$.ST0T$

$T$ TT $|0T1|1T0|0|$

II$.$

Consider the following context free grammar: $G=(\{S,A,a,b\},\{a,b\},R,S),$ where

$S$aAS

$Sa$

$A$SbA

$ASS$

$Aba,$

$($a$)$ Answer each of the following questions True or False:

$($i$)$ From the fact that $G$ is context free, it follows that there is no regular expression for $L(G).$

$($ii$)$ L$($G$)$ contains no strings of length $3.$

$($iii$)$ For any string winL$(G),$ there exists $u,v,x,y,z$ such that $w=$uvxyz,$|vy|1,$ and $u{v}^{n}x{y}^n$zinL$(G)$ for all $n0.$

$($iv$)$ If there exist languages L$1$ and L$2$ such that $L(G)=L1L2,$ then $L1$ and $L2$ must both be context free.

$($v$)$ The language $(L(G){)}^{R^R}$ is context free.

$($b$)$ Give a leftmost derivation according to $G$ of aaaabaa.

$($c$)$ Give the parse tree corresponding to the derivation in $($b$).$

III. Convert to Chomsky Normal Form:

$S$AbA

$AAa|||$