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.

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

$\begin{array}{l}A→BAB|B|\mathrm{Î\mu }\\ B→00|\mathrm{Î\mu }\\ \end{array}$

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

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 B be the language of all palindromes over {0,1} containing equal numbers of 0s and 1s. Show that B is not context free.