which are specific instances of (11.8), and
coming from (11.9). Then the next steps in the derivation are
The sequence of first indices remains the same, always remembering the initial
input. The sequence of the other indices is
0aa , a0 , a1a ,
which is equivalent to the sequence of instantaneous descriptions in (11.14).
Finally, (11.10) to (11.13) are used in the last steps
The construction described in (11.6) to (11.13) is the basis of the proof of the
following result.
Theorem 11.7
For every recursively enumerable language L, there exists an unrestricted
grammar G, such that L = L(G).
Proof: The construction described guarantees that
then
where e (x) denotes the encoding of a string according to the given convention.
By an induction on the number of steps, we can then show that