[Overview] [Previous] [Next]

From Turing Machines To Grammars II

Recall that a Turing machine accepts a string w if

q₀w xq_fy

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:

1. Initialization. These productions construct the string ...#$xq_fy#... where # indicates a blank and $ is a special variable used for termination.
2. Execution. For each transition rule of we need a corresponding production.
3. Cleanup. Our derivation will leave some excess symbols q₀, #, 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).