CSE 322 Assignment #1
Winter 1998

Due: Friday, January 16, 1998.

Reading assignment: Read Sipser's book, section 1.1; you should already have read Chapter 0. The following problems are from the First Edition of the text.

Problems:

  1. Page 27, Problem 0.10

  2. Page 27, Problem 0.11

  3. Page 83, Exercise 1.2

  4. Page 84, Exercise 1.3

  5. Page 84, Exercise 1.4. Parts (a), (b), (c), (d), (e), (f), (i), (l).
    As documentation for your DFAs, for each state write a very brief description of the set of strings that reach each state.

  6. Do the same as Exercise 1.4 Part (d), but do it for those strings that have a 0 in the third from last position rather than in the third position.

  7. For Example 1.4 in the text, write out the sequence of states that machine M4 goes through in computing on input string abaab and for input string bbaab.