CSC 456/656 Assignment 10

Due date, November 14 and November 19, 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.

This assignment is a continuation of Assignment 9. The goal is to prove that the grammar equivalence problem is undecidable. We continue to use the definition of Turing Machine given on page 319 of our textbook, and the definition of ID on page 320 of our textbook.

Due November 14:
  1. Define a list of IDs of M to be a string of the form x0# x1# ... xn such that each xi# is an ID of M.
    Using the statements of Assignment 9. prove that L1, the set of all lists of IDs of M, is a regular language. Confused notation?
Due November 19:
  1. We define a valid computation of M with input w to be a list of IDs of M such that
    1. x0 = q0w
    2. for all i > 0, xi is the subsequent of xi-1.
    3. xn, the last ID in the list, is a final ID for M.
  2. Prove that L2, the set of all lists of IDs of M which are not valid computations of M with input w, is a context-free language.
  3. Prove that L1 = L2 if and only if M does not accept w.
  4. Show how the halting problem reduces to the grammar equivalence problem, yielding a proof that the grammar equivalence problem is undecidable.
    Hint: every regular language has a context-free grammar.

Back to Course Page