each step in the example to see what the various productions do and why they
are needed.
Example 11.1
Let M = (Q, Σ, Γ, δ, q 0 , ,F) be a Turing machine with
Q = {q 0 ,q l },
Γ = {a, b, },
Σ = {a, b},
F = {q 1 }
and
δ(q 0 , a) = (q 0 , a, R),
δ(q 0 , ) = (q 1 , , L).
This machine accepts L (aa*).
Consider now the computation
which accepts the string aa. To derive this string with G, we first use rules of the
form (11.6) and (11.7) to get the appropriate starting string,
The last sentential form is the starting point for the part of the derivation that
mimics the computation of the Turing machine. It contains the original input aa
in the sequence of first indices and the initial instantaneous description q 0 aa in
the remaining indices. Next, we apply
and