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
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 grammar 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$.