318 COMPUTATIONAL COMPLEXITY
Conversely, let L E AKPA GE(n). W e may assume that there is a one-
tape NTM M1 that accepts L whose accepting computation path does not
read any symbol beyond the two blanks surrounding the input u). (A one-
worktape NTM A& which operates within space n can be easily converted to
an equivalent one-tape NTM A&, using two tracks to simulate the two tapes
of Mz.) We need to construct a context-sensitive grammar to simulate the
computation of Ml.
In Theorems 4.19 and 4.20, we showed how to construct, from a given
DTM M, an unrestricted grammar G such that L(G) = L(M). It is easy to
verify that the same construction works for an NTM M. In the following,
we further convert the grammar corresponding to NTM M, to an equivalent
context-sensitive grammar. First, for each pair (a, a) E Q x C, we define a
nontermial symbol q#a. (For the sake of readability, we write I q#a for the
symbol q#a.) Then, we define a grammar Gr with the following rules:
(A) For each instruction (p, b, L) E S(q, a) of Ml, G1 has the rules
(B) For each instruction (p, b, R) E 6(q, a) of Ml, G1 has the rules
That is, the grammar G1 is just the grammar GM~ of Theorem 4.19 without
the boundary symbols [ and 1, where rules in group (A) correspond to rules
in groups (1) and (2) of GM,, and rules in group (B) correspond to rules in
group (3) of GM~. We note that, since i’& never reads any symbol beyond
the leftmost blank or the first blank to the right of the input, the boundary
symbols are unnecessary in our case. In other words, the second type of rules
in group (3) of GM,, p/J + b pp#B], will never be used.
In addition, in the proof of Theorem 4.19, the second type of rules in
!wUP (a), c pi&q1 + II p#c ] (if (p,B, R) E S(q, a)), is to allow the tape
configurations of the machine &!I to shrink. We eliminate these rules in
grammar G1 here. Thus, Gr still simulates the computation of A& except
that its sentential forms keep all trailing blanks we have ever visited.
From the above analysis, we can see that
(4, XEY) CL, (P, &i) i an f d only if x El q#u y 3 G1 2’ El p#b y’,
where y’ retains the trailing blanks.
Now, we define grammar G2 as follows: It includes all reversals of the rules
of Gr, plus the following rules:
S __) B[h#BIT, T+BTIB,i-z-l s B ----+Lh, a Lh __) Lh a,