[Overview] [Previous] [Next]

From Turing Machines To Grammars II

Recall that a Turing machine accepts a string w if

q0w move zero or more times to xqfy

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 ...#$xqfy#... where # indicates a blank and $ is a special variable used for termination.
  2. Execution. For each transition rule of delta we need a corresponding production.
  3. 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 up.

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

For the variables V of the grammar we will use

Copyright 1996 by David Matuszek
Last modified Apr 8, 1996