The solution effectively uses the variables A and B as messengers. An A is
created on the left, travels to the right to the first c, where it creates another b
and c. It then sends the messenger B back to the left in order to create the
corresponding a. The process is very similar to the way one might program a
Turing machine to accept the language L.
Since the language in the previous example is not context-free, we see that
the family of context-free languages is a proper subset of the family of contextsensitive languages. Example 11.2 also shows that it is not an easy matter to find
a context-sensitive grammar even for relatively simple examples. Often the
solution is most easily obtained by starting with a Turing machine program, then
finding an equivalent grammar for it. A few examples will show that, whenever
the language is context-sensitive, the corresponding Turing machine has
predictable space requirements; in particular, it can be viewed as a linear
bounded automaton.
Theorem 11.8
For every context-sensitive language L not including λ, there exists some linear
bounded automaton M such that L = L (M).
Proof: If L is context-sensitive, then there exists a context-sensitive grammar for
L − {λ}. We show that derivations in this grammar can be simulated by a linear
bounded automaton. The linear bounded automaton will have two tracks, one
containing the input string w, the other containing the sentential forms derived
using G. A key point of this argument is that no possible sentential form can
have length greater than |w|. Another point to notice is that a linear bounded
automaton is, by definition, non deterministic. This is necessary in the argument,
since we can claim that the correct production can always be guessed and that no
unproductive alternatives have to be pursued. Therefore, the computation
described in Theorem 11.6 can be carried out without using space except that
originally occupied by w; that is, it can be done by a linear bounded automaton.
created on the left, travels to the right to the first c, where it creates another b
and c. It then sends the messenger B back to the left in order to create the
corresponding a. The process is very similar to the way one might program a
Turing machine to accept the language L.
Since the language in the previous example is not context-free, we see that
the family of context-free languages is a proper subset of the family of contextsensitive languages. Example 11.2 also shows that it is not an easy matter to find
a context-sensitive grammar even for relatively simple examples. Often the
solution is most easily obtained by starting with a Turing machine program, then
finding an equivalent grammar for it. A few examples will show that, whenever
the language is context-sensitive, the corresponding Turing machine has
predictable space requirements; in particular, it can be viewed as a linear
bounded automaton.
Theorem 11.8
For every context-sensitive language L not including λ, there exists some linear
bounded automaton M such that L = L (M).
Proof: If L is context-sensitive, then there exists a context-sensitive grammar for
L − {λ}. We show that derivations in this grammar can be simulated by a linear
bounded automaton. The linear bounded automaton will have two tracks, one
containing the input string w, the other containing the sentential forms derived
using G. A key point of this argument is that no possible sentential form can
have length greater than |w|. Another point to notice is that a linear bounded
automaton is, by definition, non deterministic. This is necessary in the argument,
since we can claim that the correct production can always be guessed and that no
unproductive alternatives have to be pursued. Therefore, the computation
described in Theorem 11.6 can be carried out without using space except that
originally occupied by w; that is, it can be done by a linear bounded automaton.