A grammer generating {ai | i is a positive power of 2 }
1. S Þ ACaB
2. Ca Þ aaC
3. CB Þ DB
4. CB Þ E
5. aD Þ Da
6. AD Þ AC
7. aE Þ Ea
8. AE Þ L
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.