Revised CSE 322 Assignment #5
Winter 1999

Due: Friday, February 26, 1999.

Reading assignment: Read Lewis and Papdimitriou 3.1-3.3.

Problems:

1. For each of the following languages show that it is not regular (i) using the pumping lemma (ii) using the Myhill-Nerode theorem as in example 2.5.2 of the text.

   1. { w | w=w^R }

   2. { a^mbⁿ | m >=n }

   3. { a²ⁿ | n>= 0}

2. Lewis and Papadimitriou problem 2.4.2 page 90.

3. Lewis and Papadimitriou problem 3.1.3, page 120. Document each non-terminal symbol.

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

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

6. 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.

7. (Bonus) Show that the pumping lemma cannot be used to show that

   { aⁱ b^j c^k | i, j, k >= 0, and if i = 1 then j = k }

   is not regular but show that the Myhill-Nerode can be used to prove that it isn't regular.

8. (Bonus) Lewis and Papadimitriou problem 2.4.12 page 92.