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}:nin 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
