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

On Apr 28, 4:13 pm, Lech Duraj <ldu...@xxxxxxxxxxxxxxxxxxxxxxxxxx>
wrote:
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.

Right. According Aho&Ullman CSG is defined with the only restriction
on the lengths of the words on the LHS and the RHS of the rule:

alpha <- beta

|alpha| <= |beta|

Therefore, even ab=ba is a valid rule in Aho&Ullman sense. Then,
exercise 2.1.5 introduces "true" CSG (e.g. as defined on wikipedia
page) and suggests that there is no loss of generality.
.