7i : S ® aX, X ®
Xb | l
7ii: S ® XY, X ®
aX | l , Y ®
bY | l
7iii: S ® baaS | aabS | l
8i: S ® aS | baS | bbaS | b | bb
| l
8ii: S ® XbXbX | XbXbXbX, X ®
aX | l
8iii: (same as b*a*) S ® XY, X
®
bX | l, Y ® aY
| l
Chapter 14
4i: anb2n , n = 0,1, ...
4ii: S ® aSbb | l
4iii: no, by the pumping lemma for regular languages