6.5 Context-Sensitive Languages 317
Theorem 6.35 The class of context-sensitiue languages is exactly the class
NSPACE(n).
Proof. First, assume that G is a context-sensitive grammar. We need to
construct a standard one-worktape NTM M to accept all strings w E L(G)
in space O(n). Intuitively, the NTM M keeps a sentential form a on its
work tape, and nondeterministically applies the rules of grammar G to derive
the next sentential form until it is equal to the input. Since G is context-
sensitive, the lengths of the sentential forms in a derivation are nondecreasing.
Therefore, the successful computation of this NTM only uses n cells.
More formally, the NTM M works on a nonempty input w as follows:
(1) Write down S on the work tape. Let a be the string S.(a> Repeat the following steps until one of the rejecting or accepting condi-
tions is met:
(a) Nondeterministically select a grammar rule u + v of G.
(b) Find the first occurrence of the substring u in the string a currently
on the work tape, and replace it by v. (If u does not occur in a,
then this computation rejects.) Let p be the new string on the work
tape.
(c) Compare the string ,8 with the input w. If w = ,8, then accept the
input. If IpI > 1~1, then this computation rejects. Otherwise, let
Q := ,8 and continue.We note that if w E L(G), th en there is a leftmost derivation for w:
Correspondingly, there is a computation path of M on input w in which the
strings a written on the work tape at step (2b) are exactly the strings ~0,
W,***,%?I of the leftmost derivation of w. Furthermore, the sentential forms
in the leftmost derivation never shrink, and so this computation path never
rejects at step (2~)) and will eventually accept when c! = w.
In addition, it is easy to check that the NTM M works within space bound
n + c, where c is the maximum length of the right-hand side of any rule in G.
Note that, in step (2b), where we substitute a string v for a substring u of a,
if Iv1 = IuI, then th is substitution is simple. If Iv1 > IuI, then we need to move
the nonblank symbols to the right of a to the right to create extra space for
v. This can be done by a DTM like the one studied in Example 4.9, which
does not use extra space. Therefore, M never visits more than n + c cells in
the work tape. It follows from Theorem 6.26 that L(G) E NSPACE(n).5
5 Actually, fr om the definition of the space corn
that the accepting computation path of IM on w
in rejecting paths is irrelevant.
plexi ty of an N TM, we only need to verify
uses space n. The amount of space used