CSE 322 Assignment #2
Spring 2000

Due: Friday, April 14, 2000.

Reading assignment: Read Lewis and Papdimitriou sections 2.1 and 2.2

Problems:

1. Write regular expressions for each of the following languages over the alphabet {0,1}. You do not need to justify your answers.

   1. The set of all strings that contain 0010 as a substring.

   2. The set of all strings that contain both 00 and 11 as substrings.

   3. The set of all strings that contain both 010 and 101 as substrings.

   4. The set of all strings that do not contain 101 as a substring.

   5. The set of all strings that have a 1 in the third from last position.

2. Show the computation of the DFA in Figure 2-3 on page 60 of the text on input abbaabbba.

3. Design DFA's for each of the languages in question 1. As documentation for your DFA's, for each state write a very brief description of the set of strings that reach that state.

4. Design an NFA with 4 states that accepts the set of all strings over {0,1} that contain either 00 or 11. Document your machine. This documentation is the set of strings that can reach each state (except that these sets may overlap).