0
$\begingroup$

This question is an exact duplicate of:

Disclaimer: This is a homework question.
Given the language $L=\{a^{2^n}| n\in\mathbb{N}\}$:
1. find a corresponding grammar
2. give a derivation of $a^{2^3}$
3. In which Chomsky hierarchy is this language? arguments sufficient, no proof needed.

I start with my thoughts on the 3rd task:
L obviously violates to Pumping Lemma for CFG, because you either violate after one pumping up, or you pumped the entire word and will violate it for the 2nd pump. By this, it must be recursively enumerable (Chomsky 0) or context-sensitive (Chomsky 1).
I personally think that the language belongs to the 0th hierarchy and giving an excepting Turing machine is easy with one assistant and one input tape.

Anyway, I fail completely for finding a corresponding grammar and have also no argument to give a final answer about hierarchy 1. Any hints for the grammar?

$\endgroup$

marked as duplicate by xskxzr, rici, Community May 18 at 14:29

This question was marked as an exact duplicate of an existing question.