[Overview] [Previous] [Next]

From Turing Machines To Grammars III

Initialization. We need to be able to generate any string of the form
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