CSE 322 Assignment #7
Winter 1999

Due: Friday, March 12, 1999.

Problems:

1. Lewis and Papadimitriou Problem 3.6.3 page 157.

2. 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-> AB | BA | AT | BU | SS

   • T -> SB

   • U -> SA

   • A-> a

   • B-> b

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