Convert the following CFG into an equivalent CFG in Chomsky normal form, using the procedure given in Theorem \(2.9 .\) $$ \begin{aligned} &A \rightarrow B A B|B| \varepsilon \\ &B \rightarrow 00 \mid \varepsilon \end{aligned} $$

Let \(G=(V, \Sigma, R,\langle\mathrm{STMT}\rangle)\) be the following grammar. $$ \begin{aligned} \langle\mathrm{STMT}\rangle & \rightarrow\langle\mathrm{ASSIGN}\rangle|\langle\mathrm{IF}-\mathrm{THEN}\rangle|\langle\mathrm{IF}-\mathrm{THEN}-\mathrm{ELSE}\rangle \\\ \langle\mathrm{IF}-\mathrm{THEN}\rangle & \rightarrow \text { if condition then }\langle\mathrm{STMT}\rangle \\ \langle\mathrm{IF}-\mathrm{THEN}-\mathrm{ELSE}\rangle & \rightarrow \text { if condition then }\langle\mathrm{STMT}\rangle \text { else }\langle\mathrm{STMT}\rangle \\ \langle\mathrm{ASSIGN}\rangle & \rightarrow \mathrm{a}:=1 \\ \Sigma=&\\{\text { if, condition, then, else, a:=1 }\\} \\ V=&\\{\langle\mathrm{STMT}\rangle,\langle\mathrm{IF}-\mathrm{THEN}\rangle,\langle\mathrm{IF}-\mathrm{THEN}-\mathrm{ELSE}\rangle,\langle\mathrm{ASSIGN}\rangle\\} \end{aligned} $$ \(G\) is a natural-looking grammar for a fragment of a programming language, but \(G\) is ambiguous. a. Show that \(G\) is ambiguous. b. Give a new unambiguous grammar for the same language.

Show that the class of context-free languages is closed under the regular operations, union, concatenation, and star.

Use the results of Exercise \(2.16\) to give another proof that every regular language is context free, by showing how to convert a regular expression directly to an equivalent context-free grammar.

Let \(G\) be the following grammar: $$ \begin{aligned} &S \rightarrow T \dashv \\ &T \rightarrow T \mathrm{a} T \mathrm{~b}|T \mathrm{~b} T \mathrm{a}| \varepsilon \end{aligned} $$ a. Show that \(L(G)=\\{w-1 \mid w\) contains equal numbers of a's and b's $\\} .\( Use a proof by induction on the length of \)w$. b. Use the \(D K\)-test to show that \(G\) is a DCFG. c. Describe a DPDA that recognizes \(L(G)\).

Let \(C=\left\\{w w^{\mathcal{R}} \mid w \in\\{0,1\\}^{*}\right\\} .\) Prove that \(C\) is not a DCFL. (Hint: Suppose that when some DPDA \(P\) is started in state \(q\) with symbol \(x\) on the top of its stack, \(P\) never pops its stack below \(x\), no matter what input string \(P\) reads from that point on. In that case, the contents of \(P\) 's stack at that point cannot affect its subsequent behavior, so \(P\) 's subsequent behavior can depend only on \(q\) and \(x\).)