CSE 322 Assignment #4
Winter 1999

Due: Friday, February 5, 1999.

Reading assignment: Read Lewis and Papdimitriou 2.3 and 2.4

Problems:

1. Lewis and Papdimitriou 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 (b), page 83-84.

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

5. Use the following construction to create a regular expression representing those binary strings that do not contain 0100.

   1. Design a (pattern matching) DFA that accepts all binary strings that do contain 0100.

   2. Use the construction for closure under complement to create a DFA that accepts all binary strings that do not contain 0100.

   3. Apply the construction given in lecture to create a regular expression for the language accepted by the DFA from part (b).

6. Prove that the language {aⁿ b³ⁿ : n >= 0 } is not regular.

7. (Bonus) Lewis and Papadimitriou Problem 2.3.3, page 83.

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

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

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