CSC 456/656 Assignment 9, modified November 16, 2002.

Due date, November 12, 2002, 4:00 PM.

All assignments must be handwritten (not typed or printed from a computer file) in your own handwriting, on 8.5 by 11 inch paper. Write your name on each sheet, and do not fold the pages or crimp the corners. Turn the pages in to me or to the graduate assistant on the due date.

We will use a slight variation of the definition of Turing Machine given on page 319 of our textbook. As given in class, M will not be allowed to scan to the left of the initial cell. That is, the tape is infinite to the right, and has no cells to the left of the initial (leftmost) cell.
If M is a Turing Machine, an ID of M is defined on page 320 of our textbook, but with an appropriate variation - blank cells at the beginning of the tape are indicated by the symbol B. For example, if the machine is scanning the second cell and is in state q, and the first three cells contain blank, a, and b, then the ID is Baqb, not aqb.
Fix a Turing Machine M. Let Sigma be the input alphabet of M.
  1. Prove that the set of all IDs of M is a regular language. (Be sure to tell me what the alphabet for that language is.)
  2. A final ID is an ID whose state is in F. (See page 326 of your textbook.)
    Prove that the set of all final IDs of M is a regular language.
  3. An initial ID of M is an ID of the form q0w where w is any string over Sigma and q0 is the start state.
    Prove that the set of initial IDs of M is a regular language.
  4. If x and y are IDs of M, we say that y is the successor of x if, given that the ID of M is x at a given step, the ID at the next step will be y.
    Prove that Lnotsuc, the set of all strings of the form x#y such that x and y are IDs of M and x is not the successor of y, is a context-free language.

Back to Course Page