[Overview] [Previous] [Next]

From Turing Machines To Grammars III

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

Execution. For each transition rule of we need a corresponding production. For each rule of the form
     (q_i, a) = (q_j, b, R)
we use a production
     bq_j q_ia
and for each rule of the form
     (q_i, a) = (q_j, b, L)
we use a production
     q_jcb cq_ia
for every c (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 #...#$q₀w#...#, so we need productions to get rid of everything but the w:
     #
     $q₀