Lecture: CFL$-$PDA

$1.(20$ points$)$

Give context$-$free grammars that generate the following languages. In all parts, the alphabet $\backslash$Sigma is $\{0,1\}.$

a$.\{$w$|$ w starts and ends with the same symbol$\}$

b$.\{$w$|$ w $=$ wR$,$ that is$,$ w is a palindrome$\}$

Lecture: CFL$-$PDA

$2.(20$ points$)$

Give a context$-$free grammar that generates the language

A $=\{$aibjck$|$ i $=$ j or j $=$ k where i$,$ j$,$ k $>=0\}.$

Is your grammar ambiguous? Why or why not? $($if yes, please draw the parse trees.$)$

Lecture: CFL$-$PDA

$3.(20$ points$)$

Convert the following CFG into an equivalent CFG in Chomsky normal form, using the procedure given in Theorem $2\mathrm{.}9.$

A $->$ BAB $|$ B $|\backslash$epsi

B $->00|\backslash$epsi

Lecture: CFL$-$PDA

$4.(20$ points$)$

Show that if G is a CFG in Chomsky normal form, then for any string w in L$($G$)$ of length n $>=1,$ exactly $2$n $1$ steps are required for any derivation of w$.$

Lecture: non$-$CFL

$5.(20$ points$)$

Let $\backslash$Sigma $=\{1,2,3,4\}$ and C $=\{$w in $\backslash$Sigma $|$ in w$,$ the number of $1$s equals the number of $2$s$,$ and the number of $3$s equals the number of $4$s$\}.$ Show that C is not context free.

Please make sure to choose an appropriate string S in your proof.