Context Sensitive (Type 1) Grammar for a power of two number of 'a's I'm in a introductory computational theory class and in an assignment we had a question to find both a Turing Machine that accepts and a Grammar that describes the language:
$$
\{ { a }^{ 2^{ { i } } }:\quad i\quad \ge \quad 1\} 
$$
I was able to find the Turing Machine and a Type 0 (Unrestricted) Grammar. However, my professor hinted that a Context Sensitive solution was possible. I'm curious as to how it would be done.
Thanks
 A: Here’s a monotonic grammar that does the trick, and it’s well known that monotonic and context-sensitive grammars generate the same class of languages. An algorithm for converting a monotonic grammar to an equivalent context-sensitive language is sketched here.
$$\begin{align*}
S&\to BXAE\mid aa\mid aaaa\\
XA&\to AAX\\
XE&\to YAAE\mid ZAAA\\
AY&\to YA\\
BY&\to BXA\\
AZ&\to ZA\\
BZ&\to AAA\\
A&\to a
\end{align*}$$
The idea is that $B$ and $E$ mark the beginning and the end of the string; they will eventually count as $a$’s. $X$, which will eventually count as an $a$, moves from left to right doubling the $A$’s until it reaches $E$. There it either turns into $Y$ and leaves an $A$ to double the $E$ and another to double itself, or turns into $Z$, leaves an $A$ to double itself, and doubles the $E$ into $AA$. The $Y$ or $Z$ travels back across to the left until it reaches the $B$. The $Y$ turns back into $X$ and leaves an $A$ to double the $B$, placing the $A$ to its right so that the $X$ will double it on its next pass. The $Z$ simply turns into an $A$ and turns the $B$ into $AA$. Finally, all $A$’s turn into $a$. The productions $S\to aa$ and $S\to aaaa$ are needed because the shortest string generated by the main machinery is $a^8$.
