CSE 322 Assignment #8
Winter 1998

Due: Friday, March 13, 1998.

Reading assignment: Read Sipser's book, Theorem 7.14 page 240-241. Skim section 4.2. The following problems are from the First Edition of the text.

Problems:

1. Page 121, Exercise 2.14

2. Apply the Cocke-Kasami-Younger algorithm (in proof of Theorem 7.14) to the following Chomsky Normal Form grammar to show that string babbaa is accepted (show the tableau):

   S-> AB | BA | AT | BU | SS
   T -> SB
   U -> SA
   A-> a
   B-> b
   

3. Convert the PDA given in the diagram in Figure 2.6 of the text into an equivalent CFG using the general construction of the proof of Lemma 2.15. Show your work.

4. Page 169, Exercise 4.7