====== Homework 2 ======
//Due: 21 Nov 2008//

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