316 COMPUTATIONAL COMPLEXITY
Example 6.34 Find a context-sensitive grammar for the language
L = {an2 1 n > - 1).Solution. Following the hint of Exercise 3(a) of Section 4.5, we have the
following unrestricted grammar for L:
s+ CR4 I a,
RA + AaaR, Ra + aR, RI + AL] I Ah,
aL __) La, AL + LA, [L---, [R,
a& + Lha, ALh __) Lha, [Lh + &.To see that this grammar is correct, we assume that we have a sentential
form with n copies of A’s and n2 - n copies of a’s. Then, in the next round,
we move R to the right to add one A and 2n copies of a’s. Therefore, at the
end of this round, we will have a sentential form with n + 1 copies of A’s and
( n2 -n)+2n = (n+1)2-(n+1) co p ies of a’s. The following is the derivation
of string a’:
S * [ RA] =+ [AaaR] 3 [AaaAL] =+ [AaaLA]
3 [ LAaaA] 3 [ RAaaA]^3 [AaaRaaA]^3 [Aa4RA]
3 [Aa4Aa2R] 3 [Aa4Aa2ALh 3 [Aa4Aa2Lha 3 [Lha’^3 a’.We note that only the last rule in this grammar does not have the property
that the right-hand side is at least as long as the left-hand side. If we replace
it by the rule
[Lh + aa,
then this new grammar is context-sensitive and generates the language
{ an2+2 1 n > 1). N ow, all we have to do is to modify the grammar so
that, at each-round, the sentential form has n copies of A’s and n2 - n - 2
copies of a’s. To do this, we only need to change the initial setting (and we
still add, in each round, one extra A and two a’s for each copy of A). That
is, we only change rules of the first line to
S + [RAA]lala4,
and our new grammar is context-sensitive and generates the language L.^0
From Solution 2 of Example 6.33, we can see that almost all examples and
exercises of unrestricted grammars in Section 4.5 can be converted to equiv-
alent context-sensitive grammars. Is this true for all unrestricted grammars?
In the following, we show that context-sensitive languages are exactly those
acceptable by NTM’s with a linear space bound. Thus, not all unrestricted
grammars can be converted to equivalent context-sensitive grammars, since
the unrestricted grammars generate exactly the class of r.e. languages.