[Solved]: Can context-free grammar generate $a^{2^n}$?

Problem Detail: 

Context-free grammar can generate the string a 2 n for n≥0 .

The production rule P is S→SS|a .

The derivations is, for example:

1) S⇒a (this is when n = 0)

2) S⇒SS⇒aa (this is when n = 1)

3) S⇒SS⇒SSSS⇒aaaa (this is when n = 2)

4) S⇒SS⇒SSSS⇒SSSSSSSS⇒aaaaaaaa (this is when n = 3).

Am I right?

Someone told me yes but it takes a very long time for big enough n;

someone told me no - that this grammar actually generates $a^+$ because it can be $S \Rightarrow SS \Rightarrow SSS \Rightarrow aaa$.

So, does this mean context-free grammar cannot generate the string $a^{2^n}$?

Is there exist any other context-free grammars that can generate this language?

Asked By : kate

Answered By : Shaull

It is well known (and not very difficult to prove) that a context-free language over a unary alphabet $\{a\}$ is regular.

Thus, your question is essentially, "is $\{a^{2^n}:n\in \mathbb N\}$ regular?" And the answer to that is no (easy to prove using the pumping lemma).

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/47887