CS 456/656 Assignment 4

Due date: March 22, 2007, 2:30.

All assignments must be handwritten (not typed or printed from a computer file) in your own handwriting, on 8.5 by 11 inch paper, or on A4 paper. Write your name on each sheet, and do not fold the pages or crimp the corners. (You may use a paper clip or a staple.)
Turn the pages in to me or to the graduate assistant on or before the due date.
  1. Work Exercise 3.1 on page 159 of your textbook. This exercise is on page 147 of the first edition.
  2. Work Exercise 3.8(b) on page 160 of your textbook. This exercise is on page 148 of the first edition.
  3. Draw a state diagram for a Turing machine M whose input alphabet is the binary alphabet {0,1} that shifts its input one cell to the right. That is, if the initial configuration contains a string w in the first k positions, all other cells are blank, the if the head is at the leftmost cell, then M will halt with the head at the leftmost cell, which will be blank, the next k cells will contain the string w, and all other cells will be blank.

Back to Course Page