CSE 431 Assignment #2
Spring 2003

Due: Friday, April 18, 2003.

Finish reading chapter 3 of Sipser's text and read chapter 4 of Sipser's text. The following problems are from the 1st Edition of Sipser's book.

Problems:

1. page 147, Problem 3.3

2. page 149, Problem 3.14

3. page 149, Problem 3.15

4. page 149, Problem 3.16. Hint: Handle the case where the language is finite separately from the case where it is infinite.

5. page 169, Problem 4.5. Hint: Use the pumping lemma for regular languages

6. POSTPONED

7. (Bonus) page 170, Problem 4.18