Name:

Due date: 4:00 P.M., Wednesday, March 10, 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. Find the CFG corresponding to the "syntax diagram" in Figure 6.5 of your textbook, on page 192.
2. What language over Sigma = {a,b} does the CFG with start symbol S and productions given below generate? Prove your answer.

   S --> bS | aT | Lambda

   T --> aT | bU | Lambda

   U --> aT | Lambda

3. Prove that the CFG whose productions are

   S --> aSbS | Lambda

   is unambiguous.

4. Prove that if L is a DCFL over an alphabet Sigma, then L' = Sigma* - L, the complement of L, is a CFL.
5. Use the pumping lemma for CFL's to prove that L={a^ib^jc^k | i <= j <= k} is not a CFL.