CSE 322 Assignment #3
Winter 1999

Due: Friday, January 29, 1999.

Reading assignment: Read Lewis and Papdimitriou 2.2 and 2.3

Problems:

1. Design a DFA that does pattern matching for the string x=ababbababaa 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. Draw state diagrams for NFA's that accept the languages given by the following regular expressions: Document your NFA's.

   1. ((ab)^*b)^* u b b^*

   2. (a^* b (a^* b)^* b^*)^*

   3. (a u ab)^* u (b u ba)^*

3. Lewis and Papadimitriou Problem 2.2.9, page 75.

4. Lewis and Papadimitriou Problem 2.2.10, page 75.