Thus, any context-sensitive grammar can be represented uniquely by a string
from L ((011*0)*). Furthermore, the representation is invertible in the sense that,
given any such string, there is at most one context-sensitive grammar
corresponding to it.
Let us introduce a proper ordering on {0,1} + , so we can write strings in the
order w 1 , w 2 , etc. A given string w j may not define a context-sensitive grammar;
if it does, call the grammar G j . Next, we define a language L by
L = {w i : w i defines a context-sensitive grammar G i and w i ∉ L (G i )}.
L is well defined and is in fact recursive. To see this, we construct a membership
algorithm. Given wi, we check it to see if it defines a context-sensitive grammar
G i . If not, then w i ∉ L. If the string does define a grammar, then L ( G i ) is
recursive, and we can use the membership algorithm of Theorem 11.10 to find
out if w i ∉ L (G i ). If it is not, then w i belongs to L.
But L is not context-sensitive. If it were, there would exist some w j such that
L = L (G j ). We can then ask if w j is in L (G j ). If we assume that w j ∈ L (G j ), then
by definition G j ), so we have a contradiction. Conversely, if we assume that w j ∉
L (G j ), then by definition w j ∈ L and we have another contradiction. We must
therefore conclude that L is not context-sensitive.
The result in Theorem 11.11 indicates that linear bounded automata are
indeed less powerful than Turing machines, since they accept only a proper
subset of the recursive languages. It follows from the same result that linear
bounded automata are more powerful than pushdown automata. Context-free
languages, being generated by context-free grammars, are a subset of the
context-sensitive languages. As various examples show, they are a proper subset.
Because of the essential equivalence of linear bounded automata and contextsensitive languages on one hand, and pushdown automata and context-free
languages on the other, we see that any language accepted by a pushdown
automaton is also accepted by some linear bounded automaton, but that there are
languages accepted by some linear bounded automata for which there are no
pushdown automata.
from L ((011*0)*). Furthermore, the representation is invertible in the sense that,
given any such string, there is at most one context-sensitive grammar
corresponding to it.
Let us introduce a proper ordering on {0,1} + , so we can write strings in the
order w 1 , w 2 , etc. A given string w j may not define a context-sensitive grammar;
if it does, call the grammar G j . Next, we define a language L by
L = {w i : w i defines a context-sensitive grammar G i and w i ∉ L (G i )}.
L is well defined and is in fact recursive. To see this, we construct a membership
algorithm. Given wi, we check it to see if it defines a context-sensitive grammar
G i . If not, then w i ∉ L. If the string does define a grammar, then L ( G i ) is
recursive, and we can use the membership algorithm of Theorem 11.10 to find
out if w i ∉ L (G i ). If it is not, then w i belongs to L.
But L is not context-sensitive. If it were, there would exist some w j such that
L = L (G j ). We can then ask if w j is in L (G j ). If we assume that w j ∈ L (G j ), then
by definition G j ), so we have a contradiction. Conversely, if we assume that w j ∉
L (G j ), then by definition w j ∈ L and we have another contradiction. We must
therefore conclude that L is not context-sensitive.
The result in Theorem 11.11 indicates that linear bounded automata are
indeed less powerful than Turing machines, since they accept only a proper
subset of the recursive languages. It follows from the same result that linear
bounded automata are more powerful than pushdown automata. Context-free
languages, being generated by context-free grammars, are a subset of the
context-sensitive languages. As various examples show, they are a proper subset.
Because of the essential equivalence of linear bounded automata and contextsensitive languages on one hand, and pushdown automata and context-free
languages on the other, we see that any language accepted by a pushdown
automaton is also accepted by some linear bounded automaton, but that there are
languages accepted by some linear bounded automata for which there are no
pushdown automata.