A grammer generating {ai | i is a positive power of 2 }
1. S Þ ACaB
Discussion:
A and B serve as left and right endmarkers for sentential forms;
C is a marker that moves thru the string of a's between A and B,
doubling their number by production (2).
When C hits the right endmarker B, it become either E or D by production
(3) or (4).
If (4) is chosen then the right endmarker B is consumed
and E migrates left by production (7) until it comes to the
left endmarker A and consumes A by production (8).
If (3) is chosen then D migrates left by production (5)
until the left endmarker A is reached. At that point D becomes C
by production (6), and the process starts over.
2. Ca Þ aaC
3. CB Þ DB
4. CB Þ E
5. aD Þ Da
6. AD Þ AC
7. aE Þ Ea
8. AE Þ L