Problem Solving in Automata, Languages, and Complexity

6.5 Context-Sensitive Languages 319

for all a E C, where

generates exactly the

Lh is a new nonterminal symbol. Then, grammar G2

nonempty strings u) E L as follows:

s$Bh#BlL l B$Bw cl s#B jBWLh&LhWjw.

I W I

Finally, the only rule in this grammar G:! that violates the context-sensitive

requirement is the rule BLh + &. So, we can convert Gz to an equivalent

context-sensitive grammar G by the technique of Solution 2 of Example 6.33.

That is, we can simply attach the leftmost and rightmost blanks to their

neighboring symbols and make every rule satisfying the context-sensitive re-

quirement. We leave the details to the reader as an exercise. Cl

Whether NSPACE(n) = DSPACE( n ) is, like the question of whether

NP = P, a major open question in complexity theory. (Savitch’s theorem

only gives a weaker result: NSPA CE (n) C DSPA CE (n2) .) We note, however,

that, unlike the class NP, the class NSFACE (n) is known to be closed un-

der complementation. In the following, we prove a more general result that

all classes NSPACE(s(n)) is closed under complementation, if s(n) is fully

space-constructible and s(n) 2 logn.

In order to prove this result, we first define the notion of an NTM computing

a function. We say that an NTM A4 with a write-only output tape computes

a partial function f : C + C, if the following conditions hold:

(i) For each x E Domain(f), there exists at least one accepting path of A4

on input 2.

(ii) For each x E Domain(f), every accepting path of A4 on input II: has the

same output y = f(z).

(iii) For each x # Domain(f), th ere is no accepting path in the computation

tree of A4 on input z.

In other words, an NTM A4 is considered as a transducer only if all of its

accepting paths on an input x have the same output value.

* Theorem 6.36 For any fully space-constructible function s(n) > logn,

NSPACE(s(n)) = co-NSPACE(s(n)).

Proof. Let A4 be a one-worktape NTM with the space bound s(n). Recall

the predicate read-@, p, Ic) defined in the proof of Savitch’s theorem. In this

proof, we further explore the concept of reachable configurations. Consider a

fixed input II: of length n. Let C& be the class of all configurations of A4 on z

that is of length s(n). That is,

where j indicates the position of the input

configuration of the work tape. Note that

tape head, and ybz -

each configuration

is the tape

in Cz is of