CSE 322 Assignment #3
Spring 2000

Due: Friday, April 21, 1999.

Reading assignment: Read Lewis and Papdimitriou 2.2 and 2.3

Problems:

1. Design a NFA that does pattern matching for the string x=ababaababab over the alphabet {a,b}, i.e. that accepts the language of all strings w over {a,b} that contain x as a substring.

2. Use the subset construction to convert the machine from question 1 to yield a DFA that does pattern matching for the same string. (Name the states of your DFA so that it is clear that you have used the subset construction.)

3. Lewis and Papadimitriou Problem 2.2.6, page 74-75.

4. Lewis and Papadimitriou Problem 2.2.9, page 75.

5. Lewis and Papadimitriou Problem 2.2.10, page 75.