Theorem 11.9
If a language L is accepted by some linear bounded automaton M, then there
exists a context-sensitive grammar that generates L.
Proof: The construction here is similar to that in Theorem 11.7. All productions
generated in Theorem 11.7 are non contracting except (11.13),
→ λ.
But this production can be omitted. It is necessary only when the Turing
machine moves outside the bounds of the original input, which is not the case
here. The grammar obtained by the construction without this unnecessary
production is non contracting, completing the argument.
Relation Between Recursive and Context-Sensitive
Languages
Theorem 11.9 tells us that every context-sensitive language is accepted by some
Turing machine and is therefore recursively enumerable. Theorem 11.10 follows
easily from this.
Theorem 11.10
Every context-sensitive language L is recursive.
Proof: Consider the context-sensitive language L with an associated contextsensitive grammar G, and look at a derivation of w
We can assume without any loss of generality that all sentential forms in a single
derivation are different; that is, x i ≠ x j for all i ≠ j. The crux of our argument is
that the number of steps in any derivation is a bounded function of |w|. We know
that
If a language L is accepted by some linear bounded automaton M, then there
exists a context-sensitive grammar that generates L.
Proof: The construction here is similar to that in Theorem 11.7. All productions
generated in Theorem 11.7 are non contracting except (11.13),
→ λ.
But this production can be omitted. It is necessary only when the Turing
machine moves outside the bounds of the original input, which is not the case
here. The grammar obtained by the construction without this unnecessary
production is non contracting, completing the argument.
Relation Between Recursive and Context-Sensitive
Languages
Theorem 11.9 tells us that every context-sensitive language is accepted by some
Turing machine and is therefore recursively enumerable. Theorem 11.10 follows
easily from this.
Theorem 11.10
Every context-sensitive language L is recursive.
Proof: Consider the context-sensitive language L with an associated contextsensitive grammar G, and look at a derivation of w
We can assume without any loss of generality that all sentential forms in a single
derivation are different; that is, x i ≠ x j for all i ≠ j. The crux of our argument is
that the number of steps in any derivation is a bounded function of |w|. We know
that