91Ó°ÊÓ

Give an informal description of a pushdown automaton that recognizes the language in Exercise 2.9.

Convert the CFG given in Exercise 2.1 to an equivalent PDA, using the procedure given in Theorem 2.20

Convert the CFG given in Exercise 2.3 to an equivalent PDA, using the procedure given in Theorem 2.20.

Convert the CFG given in Exercise 2.3 to an equivalent PDA, using the procedure given in Theorem 2.20.

Let $\mathbf{G}\mathbf{=}\mathbf{(}\mathbf{V}\mathbf{,}\mathbf{Î\pounds }\mathbf{,}\mathbf{R}\mathbf{,}\mathbf{S}\mathbf{)}$be the following grammar. $\mathbf{V}\mathbf{=}\mathbf{\{}\mathbf{S}\mathbf{,}\mathbf{T}\mathbf{,}\mathbf{U}\mathbf{\}}\mathbf{;}\mathbf{Î\pounds }\mathbf{=}\mathbf{\{}\mathbf{0}\mathbf{,}\mathbf{\#}\mathbf{\}}\mathbf{;}$R is the set of rules:

$\begin{array}{l}\mathbf{S}\mathbf{→}\mathbf{T}\mathbf{T}\mathbf{|}\mathbf{U}\\ \mathbf{T}\mathbf{→}\mathbf{0}\mathbf{T}\mathbf{\left|}\mathbf{T}\mathbf{0}\mathbf{\right|}\mathbf{\#}\\ \mathbf{U}\mathbf{→}\mathbf{0}\mathbf{U}\mathbf{00}\mathbf{|}\mathbf{\#}\end{array}$

a. Describe$\mathit{L}\mathbf{\left(}\mathbf{G}\mathbf{\right)}$ in English.

b. Prove that$\mathit{L}\mathbf{\left(}\mathbf{G}\mathbf{\right)}$is not regular.

Convert the following CFG into an equivalent CFG in Chomsky normal form, using the procedure given in Theorem 2.9.

$$\begin{gathered} \mathit{A}\mathbf{→}\mathit{B}\mathit{A}\mathit{B}\mathbf{\left|}\mathit{B}\mathbf{\right|}\mathit{Î\mu } \\ \mathit{B}\mathbf{→}\mathbf{00}\mathbf{|}\mathit{Î\mu } \end{gathered}$$

Recall the CFG G4 that we gave in Example 2.4. For convenience, let’s rename its variables with single letters as follows.
$$\begin{gathered} \mathit{E}\mathbf{→}\mathit{E}\mathbf{+}\mathit{T}\mathbf{}\overline{)\mathbf{T}} \\ \mathit{T}\mathbf{→}\mathit{T}\mathbf{×}\mathit{F}\mathbf{}\overline{)\mathbf{F}} \\ \mathit{F}\mathbf{→}\mathbf{\left(}\mathbf{E}\mathbf{\right)}\mathbf{}\overline{)\mathbf{a}} \end{gathered}$$

Give parse trees and derivations for each string.

a. a

b. a+a

c. a+a+a

d. ((a))

Let $\mathit{D}\mathbf{=}\mathbf{\left\{}\mathit{x}\mathit{y}\mathbf{\right|}\mathit{x}\mathbf{,}\mathit{y}\mathbf{∈}\left\{0,1\right\}\mathbf{*}\mathit{a}\mathit{n}\mathit{d}\left|x\right|\mathbf{=}\left|y\right|\mathit{b}\mathit{u}\mathit{t}\mathit{x}\mathbf{≠}\mathit{y}\mathbf{\}}\mathbf{.}{\mathit{X}}_{\mathbf{1}}\mathbf{,}\mathbf{…}\mathbf{,}{\mathit{X}}_{\mathbf{n}}$Show that$\mathit{D}$ is a context-free language.

Let $\mathit{E}\mathbf{=}\left\{a^i{b}^j|i≠jand2i≠j\right\}$. Show that$\mathit{E}$ is context-free language.

Let $\mathit{G}\mathbf{=}\mathbf{(}\mathit{V}\mathbf{,}\mathit{Î\pounds }\mathbf{,}\mathit{R}\mathbf{,}\mathbf{⟨}\mathbf{S}\mathbf{T}\mathbf{M}\mathbf{T}\mathbf{âŸ\copyright }\mathbf{)}$be the following grammar.

$\begin{array}{c}\mathbf{⟨}\mathbf{S}\mathbf{T}\mathbf{M}\mathbf{T}\mathbf{âŸ\copyright }\mathbf{→}\mathbf{⟨}\mathbf{A}\mathbf{S}\mathbf{S}\mathbf{I}\mathbf{G}\mathbf{N}\mathbf{âŸ\copyright }\mathbf{\left|}\mathbf{⟨}\mathbf{I}\mathbf{F}\mathbf{-}\mathbf{T}\mathbf{H}\mathbf{E}\mathbf{N}\mathbf{âŸ\copyright }\mathbf{\right|}\mathbf{⟨}\mathbf{I}\mathbf{F}\mathbf{-}\mathbf{T}\mathbf{H}\mathbf{E}\mathbf{N}\mathbf{-}\mathbf{E}\mathbf{L}\mathbf{S}\mathbf{E}\mathbf{âŸ\copyright }\\ \mathbf{⟨}\mathbf{I}\mathbf{F}\mathbf{-}\mathbf{T}\mathbf{H}\mathbf{E}\mathbf{N}\mathbf{âŸ\copyright }\mathbf{→}\mathbf{i}\mathbf{f}\mathbf{c}\mathbf{o}\mathbf{n}\mathbf{d}\mathbf{i}\mathbf{t}\mathbf{i}\mathbf{o}\mathbf{n}\mathbf{t}\mathbf{h}\mathbf{e}\mathbf{n}\mathbf{⟨}\mathbf{S}\mathbf{T}\mathbf{M}\mathbf{T}\mathbf{âŸ\copyright }\\ \mathbf{⟨}\mathbf{I}\mathbf{F}\mathbf{-}\mathbf{T}\mathbf{H}\mathbf{E}\mathbf{N}\mathbf{-}\mathbf{E}\mathbf{L}\mathbf{S}\mathbf{E}\mathbf{âŸ\copyright }\mathbf{→}\mathbf{i}\mathbf{f}\mathbf{c}\mathbf{o}\mathbf{n}\mathbf{d}\mathbf{i}\mathbf{t}\mathbf{i}\mathbf{o}\mathbf{n}\mathbf{t}\mathbf{h}\mathbf{e}\mathbf{n}\mathbf{⟨}\mathbf{S}\mathbf{T}\mathbf{M}\mathbf{T}\mathbf{âŸ\copyright }\mathbf{e}\mathbf{l}\mathbf{s}\mathbf{e}\mathbf{⟨}\mathbf{S}\mathbf{T}\mathbf{M}\mathbf{T}\mathbf{âŸ\copyright }\\ \mathbf{⟨}\mathbf{A}\mathbf{S}\mathbf{S}\mathbf{I}\mathbf{G}\mathbf{N}\mathbf{âŸ\copyright }\mathbf{→}\mathbf{a}\mathbf{:}\mathbf{=}\mathbf{1}\end{array}$

$\begin{array}{c}\mathbf{Î\pounds }\mathbf{=}\mathbf{\{}\mathbf{i}\mathbf{f}\mathbf{,}\mathbf{c}\mathbf{o}\mathbf{n}\mathbf{d}\mathbf{i}\mathbf{t}\mathbf{i}\mathbf{o}\mathbf{n}\mathbf{,}\mathbf{t}\mathbf{h}\mathbf{e}\mathbf{n}\mathbf{,}\mathbf{e}\mathbf{l}\mathbf{s}\mathbf{e}\mathbf{,}\mathbf{a}\mathbf{:}\mathbf{=}\mathbf{1}\mathbf{\}}\\ \mathbf{V}\mathbf{=}\mathbf{\{}\mathbf{⟨}\mathbf{S}\mathbf{T}\mathbf{M}\mathbf{T}\mathbf{âŸ\copyright }\mathbf{,}\mathbf{⟨}\mathbf{I}\mathbf{F}\mathbf{-}\mathbf{T}\mathbf{H}\mathbf{E}\mathbf{N}\mathbf{âŸ\copyright }\mathbf{,}\mathbf{⟨}\mathbf{I}\mathbf{F}\mathbf{-}\mathbf{T}\mathbf{H}\mathbf{E}\mathbf{N}\mathbf{-}\mathbf{E}\mathbf{L}\mathbf{S}\mathbf{E}\mathbf{âŸ\copyright }\mathbf{,}\mathbf{⟨}\mathbf{A}\mathbf{S}\mathbf{S}\mathbf{I}\mathbf{G}\mathbf{N}\mathbf{âŸ\copyright }\mathbf{\}}\end{array}$

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