Answers to Problem 6.17(g) on page 194.

There is no unambiguous grammar for this language. In the grammar below, many strings are generated in two ways.

Let G be the grammar with terminals {a,b} and the variables {S,S_1,S_2,R,T,U,B} and the productions:

S --> S_1

S_1 --> S_1c

S_1 --> Rc

R --> Rb

R --> Tb

T --> Lambda

T --> aTb

S --> S_2

S_2 --> aS_2

S_2 --> aU

U --> aUc

U --> B

B --> bB

B --> Lambda