Re: Exercise 2.1.2 from Aho&Ulman The theory of Parsing textbook?


How about this:

S = 1 + A S B C
B C = C B
C B = B C
A B = B A
B A = A B
A C = C A
C A = A C
A = a
B = b
C = c

This is not context-sensitive grammar, but is easily converted to one - only commutators (AB = BA etc.) need to be replaced, and this is possible for non-terminals.

Lech
.