Homework 2

Due: 21 Nov 2008

1. (Sipser Ex.1.6) Describe DFAs recognizing the following languages. Let the alphabet be {0,1}.
   1. {w | w contains the substring 0101, i.e., w = x0101y for some x and y}
   2. {w | w is any string except 11 and 111}
   3. {w | every odd position of w is a 1}
   4. {w | the length of w is at most 5}
2. Use the construction described in class to give an NFA recognizing the union of languages in problem 1-I and 1-III.
3. Use the construction described in class to give an NFA recognizing the concatenation of languages in problem 1-IV and 1-II.
4. Use the construction described in class to give an NFA recognizing the star of language in problem 1-III.
5. Exercises 1.14, 1.17, 1.19 is Sipser's book.
6. Problems 1.36, 1.38, 1.41 in Sipser's book.
7. Bonus: Problem 1.42 in Sipser's book.