CSE 322 Assignment #6
Winter 1999

Due: Friday, March 5, 1999.

Reading assignment: Read Lewis and Papdimitriou sections 3.4-3.6. I will give an alternative handout for the proof of Lemma 3.4.2 and for a stronger version of Theorem 3.5.3.

Problems:

1. Carry out the general top-down construction to convert a CFG to a PDA for the grammar for balanced parentheses (Example 3.1.4 page 118-9 in the text. Now, do the same for the bottom-up construction (top of page 170 in the text) and show the accepting computations of both PDA's on input (()())().

2. Carry out the general construction to convert a PDA to a CFG for the PDA given in class for the language consisting of strings with equal numbers of a's and b's. How many rules would the general construction give for this example? There are lots of rules but you only need to write down a subset of the rules that is good enough.

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

4. Lewis and Papadimitriou Problem 3.5.8, page 149

5. Lewis and Papadimitriou Problem 3.5.14, page 149

6. Convert the following grammar to Chomsky Normal Form using our general construction:

   • S -> BSB | B | e

   • B -> 00 | e

7. Convert the following grammar to Chomsky Normal Form (REMAINDER OF QUESTION POSTPONED UNTIL NEXT WEEK: and fill out the table for the Cocke-Kasami-Younger dynamic programming algorithm when applied to input $aabababb$.)

   • S -> aSb | bSa | SS | e