From Turing Machines To Grammars II
Recall that a Turing machine accepts a string w if
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
- Initialization. These productions construct the string ...#$xqfy#...
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 q0, #, and $ in
the string (along with the desired w), so we need a few more productions to clean these
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 qi 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