Recall that a Turing machine accepts a string w if

q_{0}w
xq_{f}y

and that our grammar will run "backwards" compared to the Turing machine.

The productions of the grammar we will construct can be logically grouped into three sets:

**Initialization.**These productions construct the string ...#$xq_{f}y#... where # indicates a blank and $ is a special variable used for termination.**Execution.**For each transition rule of we need a corresponding production.**Cleanup.**Our derivation will leave some excess symbols q_{0}, #, and $ in the string (along with the desired w), so we need a few more productions to clean these up.

For the terminals T of the grammar we will use the input alphabet of the Turing machine.

For the variables V of the grammar we will use

- -, the tape alphabet minus the symbols we took for T.
- A symbol q
_{i}for each state of the Turing machine. - # (blank) and $ (used for termination).
- S (for a start symbol) and A (used for initialization).

Copyright © 1996 by David Matuszek

Last modified Apr 8, 1996