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.
theory_of_computation/homework2.txt · Last modified: 2008/11/12 01:21 by jittat
 
 
©2008 Another cool website by 80KV