6.5 Context-Sensitive Languages 321
reachable from ,& Assume that & has been computed correctly. Then, in
the computation of NI,+l, for each c1:, there exists exactly one nonrejecting
path in step (2). Indeed, only the path that guesses, in the increasing order,
the & configurations pi that are reachable from p in k moves survives the
verifications (i) and (ii). All other paths are rejecting paths. For each Q!, this
unique nonrejecting path must determine whether reach(P, a, k+ 1) correctly.
Therefore, the value NI,+i must be correct too.
In the third step, we construct a third NTM A& for L(M) as follows:
Muchine A&. First, A& simulates l& to compute the number N of
reachable configurations from the initial configuration CQ. Then,
it guesses N configurations 71,... , TN, one by one and in the in-
creasing order as in Mz above, and checks that each is reachable
from CQ (by machine Ml) and none of them is an accepting con-
figuration. It accepts if the above are checked; otherwise, it rejects
this computation path.
We claim that this machine MS accepts L(M). First, it is easy to see
that if ~xf @ L(M), th en all reachable configurations from a0 are nonaccepting
configurations. So, the computation path of MS that guesses correctly all N
reachable configurations of a0 will accept z. Conversely, if x: E L(M) , then one
of the reachable configurations from a0 must be an accepting configuration.
So, a computation path of MS must guess either all reachable configurations
that include one accepting configuration or guess at least one nonreachable
configuration. In either case, this computation path must reject. Thus, Ma
accepts exactly those IX: 4 L(M).
Finally, the same argument for Mz verifies that MS uses space 0( s( n)).
The theorem then follows from the tape compression theorem for NTM’s. 0
Corollary 6.37 If A is a context-sensitive language, then A is also context-
sensitive.
Exercise 6.5
1. Construct context-sensitive grammars for the languages of Examples
4.17 and 4.18, and for the languages in Exercises 3(b)-3(i) of Section
4.5.