Due on 14 April 2009, start of class

Please submit a paper copy in class.

CSE 355 Homework Five


  1. Sipser 3.4.
  2. Sipser 3.7.
  3. Consider the language L = {w | w contains exactly twice as many 0's as 1's} over the alphabet {0,1}. Give an implementation-level description and a low-level description of a Turing machine that decides L.
  4. Sipser 3.13.
  5. Sipser 3.14.
A PDF version is here.