Using the algorithm discussed in class, demonstrate equivalent PDAs for the following CFGs:

a) The grammar given in Problem 2.13, p156 of the text.

Let G = (V, ?, R, S) be the following grammar. V = {S, T, U}; ? = {0, #}; and R is the set of rules: S ? T T | U T ? 0T | T 0 | # U ? 0U00 | # a. Describe L(G) in English. b. Prove that L(G) is not regular.

b) The grammar given in Problem 2.14, p156 of the text.

Convert the following CFG into an equivalent CFG in Chomsky normal form, using the procedure given in Theorem 2.9. A ? BAB | B | ? B ? 00 | ?

problem 2.13: Let G = (V, ?, R, S) be the following grammar. V = {S, T, U}; ? = {0, #}; and R is the set of rules: S ? T T | U T ? 0T | T 0 | # U ? 0U00 | # a. Describe L(G) in English. b. Prove that L(G) is not regular