Construct a Turing machine for L (01 (01)*), then find an unrestricted grammar for it using the construction in Theorem 11.7. Give a derivation for 0101 using the resulting grammar.

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 if and only if We also must show that we can generate every possible starting configuration and that w is properly reconstructed if and only if M enters a final configuration. The details, which are not too difficult, are left as an exercise.