if and only if (11.3) holds. This is not hard to do; what is more difficult to see is
how to make the connection between (11.4) and what we really want, namely,
for all w satisfying (11.3). To achieve this, we construct a grammar which, in
broad outline, has the following properties:
1. S can derive q 0 w for all w ∈ Σ + .
2. (11.4) is possible if and only if (11.3) holds.
3. When a string xq f y with q f ∈ F is generated, the grammar transforms this
string into the original w.
The complete sequence of derivations is then
The third step in the above derivation is the troublesome one. How can the
grammar remember w if it is modified during the second step? We solve this by
encoding strings so that the coded version originally has two copies of w. The
first is saved, while the second is used in the steps in (11.4). When a final
configuration is entered, the grammar erases everything except the saved w.
To produce two copies of w and to handle the state symbol of M (which
eventually has to be removed by the grammar), we introduce variables V ab and
V aib for all a ∈ Σ ∪ { }, b ∈ Γ, and all i such that q i ∈ Q. The variable V ab
encodes the two symbols a and b, while V aib encodes a and b as well as the state
q i .
The first step in (11.5) can be achieved (in the encoded form) by
for all a ∈ Σ. These productions allow the grammar to generate an encoded
version of any string q 0 w with an arbitrary number of leading and trailing blanks.
For the second step, for each transition