CSE 322 Assignment #4
Spring 2000

Due: Friday, April 28, 2000.

Reading assignment: Read Lewis and Papadimitriou 2.4

Problems:

  1. Lewis and Papadimitriou Problem 2.3.1, page 83.

  2. Use the construction given in the proof that NFA's accept all regular languages to find NFA's that accept

    1. (ba* U Ø*)*

    2. (ab U a)* b*

  3. Lewis and Papadimitriou Problem 2.3.6 (a), page 83-84.

  4. Lewis and Papadimitriou Problem 2.3.6 (g), page 83-84.

  5. Lewis and Papadimitriou Problem 2.3.7 (d), page 84.

  6. Prove that the language {an b3n : n >= 0 } is not regular.

  7. (Bonus) Lewis and Papadimitriou Problem 2.3.6 (c), page 83-84.

  8. (Bonus) Lewis and Papadimitriou Problem 2.3.6 (d), page 83-84.

  9. (Bonus) Lewis and Papadimitriou Problem 2.3.6 (f), page 83-84.

  10. (Bonus) Let HALF-L={x : there is a y with |y|=|x| and xy is in L}. Show that if L is regular then so is HALF-L.