AUCSC 315 / AUMAT 355 - Assignment 5
DUE: Monday, 18 March 2013, 6:00 p.m.
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.
- 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).
Copyright © 2013
William W. Hackborn
Document last modified on