5. Give the details of the proof of Theorem 11.7.
6. 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.
7. Show that for every unrestricted grammar there exists an equivalent
unrestricted grammar, all of whose productions have the form
u → υ
with u, υ ∈(V ∪ T) + and |u| ≤ |υ|, or
A → λ,
with A ∈ V
8. Show that the conclusion of Exercise 7 still holds if we add the further
conditions |u| ≤ 2 and |υ| ≤ 2.
9. Some authors give a definition of unrestricted grammars that is not quite the
same as our Definition 11.3. In this alternate definition, the productions of an
unrestricted grammar are required to be of the form
x → y,
where
x ∈ (V ∪ T)* V (V ∪ T)*,
and
y ∈ (V ∪ T)*.
The difference is that here the left side must have at least one variable. Show that
this alternate definition is basically the same as the one we use, in the sense that
for every grammar of one type, there is an equivalent grammar of the other type.
11.3 Context-Sensitive Grammars and Languages
Between the restricted, context-free grammars and the general, unrestricted