Problem Solving in Automata, Languages, and Complexity

(^314) COMPUTATIONAL COMPLEXITY
6.5 Context-Sensitive Languages
In this section, we study a restricted type of grammars and present a charac-

terization of the space complexity of the corresponding languages. A context-

sensitive grammar is a grammar in which the right-hand side of a rule is
always at least as long as the corresponding left-hand side; that is, for any

rule a + p in this grammar, we must have lpl > 1~1. A language L is called a

context-sensitive language if L - {E) = L(G) for - some context-sensitive gram-
mar G. For instance, the language L(G) of E xample 4.15 is context-sensitive,
because we can change the rule 5’ + E to S + aBC to get a context-sensitive
grammar for L(G) - {E). Indeed, 1 ‘t can be proved that the languages of all
examples and exercises in Section 4.5 are context-sensitive. Their correspond-
ing context-sensitive grammars can be obtained from simple modifications of
their unrestricted grammars. We show some examples below.

Example 6.33 Find a context-sensitive grammar for the language

L = {a2” I n > - 0).

Solution 1. Recall the unrestricted grammar G for L given in Example 4.16:

(1) s + [Ral,

(3) Ra + aaR,

(5) R] + Lh,

(7) LL + [R,

(9) [Lh + &.

(2) s + a,

(4) RI + Ll)

(6) aL 4 La,

(8) aLh + Lha,

It is clear that the only rules that violate the context-sensitive requirement
that every rule a! + p must have l@l > lcvl are rules (5) and (9). Now, suppose
we replace them by

(5’) R] --+ Lh a, and

(9’) [Lh * aa,

then it becomes a context-sensitive grammar Gi with L(G1) = {a2n+3 I n 2

1. Thus, all we have to do now is to modify grammar G1 to always generate
   three less symbols a. This can be achieved by encoding a substring aaaa of
   a sentential form by a single nonterminal symbol Aa. When we move the
   marker R to the right to double each symbol a to aa, we treat A4 as aaaa;
   but, at the end, we only change A4 to a single symbol a. That is, the following
   grammar G2 is context-sensitive and it generates L:

S ----+ [ RAd] I a I aaaa,

Ra + aaR, RA4 + aaaaAdR, R] + L] 1 Lha,

aL ___) La, A4L + LA4, [L + [R,

dh + &a, A4Lh + Lha, [Lh + aa. Cl