CSE 322 Assignment #7
Spring 2000

Due: Friday, May 19, 2000.

Reading assignment: Read Lewis and Papdimitriou 3.3-3.4 up to the end of Lemma 3.4.1 as well as page 169-170 of the text. I will give a handout for the rest of the material in the chapter.

Problems:

1. PROBLEM CANCELLED: Lewis and Papadimitriou problem 3.1.3, page 120. Document each non-terminal symbol.

2. Lewis and Papadimitriou problem 3.1.9 page 122, parts (a), (b), (c). Document each non-terminal symbol.

3. Lewis and Papadimitriou problem 3.3.2 page 135, parts (c), (d). Use the diagram notation from class. Document the states of your PDA's.

4. Consider the following grammar for a programming language fragment:

           <STMT> ->  <ASSIGN> | <IF-THEN> | <IF-THEN-ELSE> | <BEGIN-END>
        <IF-THEN> ->  if condition then <STMT>
   <IF-THEN-ELSE> ->  if condition then <STMT> else <STMT>
      <BEGIN-END> ->  begin <STMT-LIST> end
      <STMT-LIST> ->  <STMT-LIST> <STMT> | <STMT>
         <ASSIGN> ->  a:=1
   
   where the start symbol is <STMT>.
   

   1. Show that this is actually ambiguous.

   2. (Bonus) Give a new unambiguous grammar for the same language.

5. 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 (()())().