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.
These two theorems establish what we set out to do. They show that the
family of languages associated with unrestricted grammars is identical with the
family of recursively enumerable languages.
EXERCISES
1. What language does the unrestricted grammar
S → S 1 B,
S 1 → a S 1 b
bB → bbbB,
a S 1 b → aa
B → λ
derive?
2. What difficulties would arise if we allowed the empty string as the left side of
a production in an unrestricted grammar?
3. Consider a variation on grammars in which the starting point for any
derivation can be a finite set of strings, rather than a single variable.
Formalize this concept, then investigate how such grammars relate to the
unrestricted grammars we have used here.
4. In Example 11.1, prove that the constructed grammar cannot generate any
sentence with a b in it.