91Ó°ÊÓ

Let $\mathbf{A}\mathbf{=}\mathbf{\left\{}{\mathbf{wtw}}^{\mathbf{R}}\mathbf{\right|}\mathbf{w}\mathbf{,}\mathbf{t}\mathbf{∈}{\mathbf{\{}\mathbf{0}\mathbf{,}\mathbf{1}\mathbf{\}}}^{\mathbf{*}}\mathbf{and}\mathbf{\left|}\mathbf{w}\mathbf{\right|}\mathbf{=}\mathbf{\left|}\mathbf{t}\mathbf{\right|}\mathbf{\}}\mathbf{.}$ Prove that A is not a CFL.

Consider the following CFG:

$\begin{array}{l}\mathbf{S}\mathbf{→}\mathbf{S}\mathbf{S}\mathbf{|}\mathbf{T}\\ \mathbf{T}\mathbf{→}\mathbf{a}\mathbf{T}\mathbf{b}\mathbf{|}\mathbf{a}\mathbf{b}\end{array}$

Describe $\mathit{L}\mathbf{\left(}\mathbf{G}\mathbf{\right)}$and show that G is ambiguous. Give an unambiguous grammar$\mathbf{\left(}\mathbf{H}\mathbf{\right)}$ where $\mathit{L}\mathbf{\left(}\mathbf{H}\mathbf{\right)}\mathbf{=}\mathit{L}\mathbf{\left(}\mathbf{G}\mathbf{\right)}$and sketch a proof that $\mathbf{\left(}\mathbf{H}\mathbf{\right)}$is unambiguous.

We defined the rotational closure of language $\mathbf{A}$to be $\mathbf{RC}\mathbf{\left(}\mathbf{A}\mathbf{\right)}\mathbf{=}\mathbf{\left\{}\mathbf{yx}\mathbf{\right|}\mathbf{xy}\mathbf{∈}\mathbf{A}\mathbf{\}}$ . Show that the class of CFLs is closed under rotational closure

Give context-free grammars that generate the following languages. In all parts, the alphabet $\mathbf{∑}$is $\left\{0,1\right\}$.

role="math" localid="1660714062992" $$\begin{gathered} \mathit{a}\mathbf{.}\mathbf{}\mathbf{\{}\overline{)\mathbf{w}\mathbf{}}\mathbf{}\mathbf{w}\mathbf{}\mathbf{c}\mathbf{o}\mathbf{n}\mathbf{t}\mathbf{a}\mathbf{i}\mathbf{n}\mathbf{s}\mathbf{}\mathbf{a}\mathbf{t}\mathbf{}\mathbf{l}\mathbf{e}\mathbf{a}\mathbf{s}\mathbf{t}\mathbf{}\mathbf{t}\mathbf{h}\mathbf{r}\mathbf{e}\mathbf{e}\mathbf{}\mathbf{1}\mathbf{s}\mathbf{\}} \\ \mathit{b}\mathbf{.}\mathbf{}\mathbf{\{}\overline{)\mathbf{w}\mathbf{}}\mathbf{}\mathbf{w}\mathbf{}\mathbf{s}\mathbf{t}\mathbf{a}\mathbf{r}\mathbf{t}\mathbf{s}\mathbf{}\mathbf{a}\mathbf{n}\mathbf{d}\mathbf{}\mathbf{e}\mathbf{n}\mathbf{d}\mathbf{s}\mathbf{}\mathbf{w}\mathbf{i}\mathbf{t}\mathbf{h}\mathbf{}\mathbf{t}\mathbf{h}\mathbf{e}\mathbf{}\mathbf{s}\mathbf{a}\mathbf{m}\mathbf{e}\mathbf{}\mathbf{s}\mathbf{y}\mathbf{m}\mathbf{b}\mathbf{o}\mathbf{l}\mathbf{\}} \\ \mathit{c}\mathbf{.}\mathbf{}\mathbf{\{}\overline{)\mathbf{w}\mathbf{}}\mathbf{}\mathbf{t}\mathbf{h}\mathbf{e}\mathbf{}\mathbf{l}\mathbf{e}\mathbf{n}\mathbf{g}\mathbf{t}\mathbf{h}\mathbf{}\mathbf{o}\mathbf{f}\mathbf{}\mathbf{w}\mathbf{}\mathbf{i}\mathbf{s}\mathbf{}\mathbf{o}\mathbf{d}\mathbf{d}\mathbf{\}} \\ \mathit{d}\mathbf{.}\mathbf{}\mathbf{\{}\overline{)\mathbf{w}\mathbf{}}\mathbf{}\mathbf{t}\mathbf{h}\mathbf{e}\mathbf{}\mathbf{l}\mathbf{e}\mathbf{n}\mathbf{g}\mathbf{t}\mathbf{h}\mathbf{}\mathbf{o}\mathbf{f}\mathbf{}\mathbf{w}\mathbf{}\mathbf{i}\mathbf{s}\mathbf{}\mathbf{o}\mathbf{d}\mathbf{d}\mathbf{}\mathbf{a}\mathbf{n}\mathbf{d}\mathbf{}\mathbf{i}\mathbf{t}\mathbf{s}\mathbf{}\mathbf{m}\mathbf{i}\mathbf{d}\mathbf{d}\mathbf{l}\mathbf{e}\mathbf{}\mathbf{s}\mathbf{y}\mathbf{m}\mathbf{b}\mathbf{o}\mathbf{l}\mathbf{}\mathbf{i}\mathbf{s}\mathbf{}\mathbf{a}\mathbf{}\mathbf{0}\mathbf{\}} \\ \mathit{e}\mathbf{.}\mathbf{}\mathbf{\{}\overline{)\mathbf{w}\mathbf{}}\mathbf{}\mathbf{w}\mathbf{=}{\mathbf{w}}^{\mathbf{R}}\mathbf{,}\mathbf{}\mathbf{t}\mathbf{h}\mathbf{a}\mathbf{t}\mathbf{}\mathbf{i}\mathbf{s}\mathbf{,}\mathbf{}\mathbf{w}\mathbf{}\mathbf{i}\mathbf{s}\mathbf{}\mathbf{a}\mathbf{}\mathbf{p}\mathbf{a}\mathbf{l}\mathbf{i}\mathbf{n}\mathbf{d}\mathbf{r}\mathbf{o}\mathbf{m}\mathbf{e}\mathbf{\}} \\ \mathit{f}\mathbf{.}\mathbf{}\mathit{T}\mathit{h}\mathit{e}\mathbf{}\mathit{e}\mathit{m}\mathit{p}\mathit{t}\mathit{y}\mathbf{}\mathit{s}\mathit{e}\mathit{t}\mathbf{.} \end{gathered}$$

We defined the CUT of language $\mathbf{A}$ to be $\mathbf{CUT}\mathbf{\left(}\mathbf{A}\mathbf{\right)}\mathbf{=}\mathbf{\left\{}\mathbf{yxz}\mathbf{\right|}\mathbf{xyz}\mathbf{∈}\mathbf{A}\mathbf{\}}\mathbf{.}$ Show that the class of CFLs is not closed under CUT.

Show that the class of DCFLs is not closed under the following operations:

a. Union

b. Intersection

c. Concatenation

d. Star

e. Reversal

Let G be the following grammar:

$\begin{array}{l}\mathbf{S}\mathbf{→}\mathbf{T}\mathbf{−}\mathbf{|}\\ \mathbf{T}\mathbf{→}\mathbf{T}\mathbf{a}\mathbf{T}\mathbf{b}\mathbf{\left|}\mathbf{T}\mathbf{b}\mathbf{T}\mathbf{a}\mathbf{\right|}\mathbf{Î\mu }\end{array}$

1. Show that$\mathit{L}\mathbf{\left(}\mathbf{G}\mathbf{\right)}\mathbf{=}\mathbf{\left\{}\mathbf{w}\mathbf{−}\mathbf{\left|}\mathbf{\right|}\mathbf{w}\mathbf{\text{ c´Ç²Ô³Ù²¹¾±²Ô²õ e±ç³Ü²¹±ô n³Ü³¾²ú±ð°ù o´Ú }}{\mathbf{a}}^{\mathbf{\text{'}}}\mathbf{\text{²õ a²Ô»å }}{\mathbf{b}}^{\mathbf{\text{'}}}\mathbf{\text{s}}\mathbf{\right\}}$ . Use a proof by induction on the length of W.
2. Use the DK-test to show that G is a DCFG,
3. Describe a DPDA that recognizes$\mathit{L}\mathbf{\left(}\mathbf{G}\mathbf{\right)}$

Give informal descriptions and state diagrams of pushdown automata for the languages in Exercise 2.4

Give context-free grammars generating the following languages.

1. The set of strings over the alphabet $\left\{a,b\right\}$ with more a’s than b’s.
2. The complement of the languagerole="math" localid="1660717618566" $\{a^n{b}^n\overline{)nâ‰\yen 0}\}$
3. role="math" localid="1660717878385" $\{w\#x\overline{)w^R}isasubstringofxforw.x∈\left\{0,1\right\}*\}$
4. role="math" localid="1660718125664" $\{x_1{\#}_2\#...\#x_k\overline{)kâ‰\yen 1,each{x}_i∈\left\{a,b\right\}*,andforsomeiandj,x_i=x_j^R}\}$
   

Give a context-free grammar that generates the language

$\mathit{A}\mathbf{=}\left\{a^i{b}^j{k}^k\overline{)i=j}orj=kwherei,j,kâ‰\yen 0\right\}$

Is your grammar ambiguous? Why or Why not?