Your solutions to the problems below may be either **neatly** handwritten or done on a word processor. When submitting your solutions, please number them as they are numbered below and staple them together in numerical order.

- Problem 5, chapter 12. Describe the language that this CFG generates
**both**in*English*and using a*regular expression*. Also, in addition to finding a word in this language that can be generated in two substantially different ways,**show**the*derivations*of this word.

- Problem 11, chapter 12.

- Problem 17, chapter 12. For each of the CFGs in parts (i) to (iii), show that it is ambiguous by finding a word with two distinct
*derivation trees*and**draw**those*derivation trees*. Note also that part (v) of this question uses a concept (killing Λ-*productions*) from chapter 13.

- Regular languages and regular grammars:

- Problem 1, part (iii) only, chapter 13. First create an FA for the language, and then use it to obtain a CFG.

- Problem 5, part (i) only, chapter 13. First use the CFG to obtain a TG for the language, and then use it to obtain a regular expression.

- Problem 1, part (iii) only, chapter 13. First create an FA for the language, and then use it to obtain a CFG.
- For the CFG given in problem 13, part (iii) only, chapter 13, do the following:

- Eliminate the Λ-
*production*(which produces a new CFG that defines the same language as the original CFG, except that it does not include the null word Λ).

- Starting with the CFG resulting from part A, eliminate the
*unit productions*.

- Convert the CFG resulting from part B to
*Chomsky Normal Form*. This is easy to do (basically just introduce two new non-terminals, say X and Y, that produce the two terminals).

- Eliminate the Λ-

Copyright © 2013 William W. Hackborn