of M, we put into the grammar productions
for all a, p ∈ Σ ∪ { },q ∈ Γ. For each
of M, we include in G
for all a, p ∈ Σ ∪ { },q ∈ Γ.
If in the second step, M enters a final state, the grammar must then get rid of
everything except w, which is saved in the first indices of the V’s. Therefore, for
every q j ∈ F, we include productions
for all a ∈ Σ ∪ { }, b ∈ Γ. This creates the first terminal in the string, which
then causes a rewriting in the rest by
for all a,c ∈ Σ ∪ { }, b ∈ Γ . We need one more special production
This last production takes care of the case when M moves outside that part of the
tape occupied by the input w. To make things work in this case, we must first use
(11.6) and (11.7) to generate
representing all the tape region used. The extraneous blanks are removed at the
end by (11.13).
The following example illustrates this complicated construction. Carefully check