Name:

Due date: 4:00 P.M., Wednesday, March 17, 1998.

If you cannot attend class that day, leave your homework, in an envelope, with one of the office staff, on or before Wednesday.

Please work your homework only on these pages, and turn in these pages. Do not attach extra pages. You may use one side or both sides of the paper. Use pen or pencil, any color except red. If you use pen, it is perfectly correct to simply cross out material I should ignore, rather than try to erase it. Do not fold your papers at all. If you put them in an envelope, the envelope should be 9 by 12.

You are permitted to discuss homework with other members of the class, or others outside the class. But the purpose of this discussion should be to enlighten you (or the other person, if a member of the class) about the material, not for one person to simply do another person's homework.

1. Work problem 6.43 on page 197 of your textbook. Write your answers here:
2. Let L = {a^i,b^i | i>=0}.
   1. Give the transition table of a DPDA that accepts L by final state.
   2. Prove that there is no DPDA that accepts L by empty stack.
3. A Szilard grammar is a CFG with the following properties:
   1. The right hand side of each production consists of one terminal followed by zero or more variables.
   2. Each terminal appears in exactly one production.
   Prove that every Szilard grammar is unambiguous.
4. Work problem 8.1(b) on page 251 of your textbook.