6.5 Context-Sensitive Languages 315
Solution 2. A more general technique of converting an unrestricted grammar
to a context-sensitive grammar is to “hide” the uz~iliary symbols (which will
eventually become E), such as R, L, [ and ] here, by attaching them to their
neighboring real symbols (which will eventually become terminal symbols). In
the following, we use new nonterminal symbols XAY to replace a substring
XaY in a sentential form of grammar G, where X and Y do not contain the
symbol a. Whenever it is possible, we attach an auxiliary symbol X to the
symbol a to its right. Therefore, new symbols XAY and AY are used only
when Y ends with 1. (T o make the following grammar rules readable, we
write xAy for xAy to emphasize that X and Y are attached to symbol A.)
Fol I owing the above idea, we replace rules (1) and (2) of grammar G by
the following rules:
(la) s - [RA] 7
I(2a) S __) a.
For rule (3)) we replace it by the following six rules:
(3 > a
(3 C >
(3 e )
a AR] j
El
+ [A a
cl I
RA] I