[Overview] [Previous] [Next]

From Turing Machines To Grammars III

Initialization. We need to be able to generate any string of the form
     #...#$xqfy#...#
Since we need an arbitrary number of "blanks" on either side, we use the productions
     S goes to #S | S# | $A
(The $ is a marker we will use later.) Next we use the A to generate the strings x, y is a member of gamma, with a state qf somewhere in the middle:
     A goes tosA | As | qf, for all s is a member of gamma.

Execution. For each transition rule of delta we need a corresponding production. For each rule of the form
     delta(qi, a) = (qj, b, R)
we use a production
     bqj goes to qia
and for each rule of the form
     delta(qi, a) = (qj, b, L)
we use a production
     qjcb goes to cqia
for every c is a member of gamma (the asymmetry is because the symbol to the right of q is the one under the Turing machine's tape head.)

Cleanup. We end up with a string that looks like #...#$q0w#...#, so we need productions to get rid of everything but the w:
     # goes to empty string
     $q0 goes to empty string


Copyright 1996 by David Matuszek
Last modified Apr 8, 1996