CSE 322 Assignment #8
Spring 2000

Due: Friday, May 26, 2000.

Reading assignment: Read Lewis and Papdimitriou Sections 3.5-3.6. I will give handouts on most of this material.

Problems:

1. Lewis and Papadimitriou Problem 3.5.2 (b), (d), page 148

2. Lewis and Papadimitriou Problem 3.5.8, page 149. (We proved this stronger form in class.)

3. Lewis and Papadimitriou Problem 3.5.14, page 149

4. Convert the following grammar to Chomsky Normal Form using our general construction and run the Cocke-Kasami-Younger algorithm for the input babbaa: (Show the tableau.)

   • S-> aSb | bSa | SS | e

5. (Bonus) Lewis and Papadimitriou Problem 3.1.10, page 122.