CSC 456/656 Assignment 11

Due date November 26, 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, but as modified in the previous homeworks.
We first remark that if a language L is accepted by a Turing machine M, then without loss of generality,
  1. M has just one final state (which we call h).
  2. If the input of M is some string w in L, then M will halt with all blanks on its tape, and with the head on the leftmost cell.
Now, the homework questions. Our goal is to prove that the languages generated by general grammars are precisely the recursively enumerable languages.
Let M be a Turing machine. We will assume that if w is any string in L(M), then the computation of M with input w halts with the tape blank and the head in the leftmost cell.
  1. Show that there exists a general grammar G1 such that, if y is an ID of M, then y derives x in one step using G if and only if x is an ID of M and y is the successor of x.
  2. Show that there is a general grammar G2 such that L(G2) = L(M). Hint: it is almost exactly the same as G1, and the start symbol of G2 is h.

Back to Course Page