AUCSC 315 / AUMAT 355 - Assignment 5

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.

1. 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.
   
   
2. Problem 11, chapter 12.
   
   
3. 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.
   
   
4. Regular languages and regular grammars:
   
   
   1. Problem 1, part (iii) only, chapter 13. First create an FA for the language, and then use it to obtain a CFG.
      
      
   2. 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.
      
      
5. For the CFG given in problem 13, part (iii) only, chapter 13, do the following:
   
   
   1. 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 Λ).
      
      
   2. Starting with the CFG resulting from part A, eliminate the unit productions.
      
      
   3. 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).