I have to determine, and prove, whether the language $L=\{a^{2^{n}} \mid$ n is a natural number$\}$ is context free or not (if it is by a grammar and not by the pumping lemma).

I tried to construct a grammar, but I don't have a working one. I have no problems to construct the language $L=\{a^{2n} \mid$ n is a natural number$\}$. So I tried the pumping lemma, but I don't find the proof, that this is not context free.

Can someone tell me of what type this language is? A hint how to prove this would also be very nice.

  • 1
    $\begingroup$ I do not undertand you sentence in parentheses in the first paragrapoh. Also, you should think of telling whether you consider 0 a natural number, as there is no consensus on that (but it does not matter here). Then you should look at our reference page. $\endgroup$ – babou Jun 9 '15 at 11:20
  • $\begingroup$ Hint: the pumping lemma tells you that there is a sequence of words in a CF language (an infinite one) that increase linearly in size. Can you do that with $L$. $\endgroup$ – babou Jun 9 '15 at 11:22
  • 1
    $\begingroup$ See also our reference questions. $\endgroup$ – Raphael Jun 9 '15 at 12:36
  • 5
    $\begingroup$ Hint: since all unary context-free languages are regular, it is sufficient to show that the language is not regular. $\endgroup$ – Raphael Jun 9 '15 at 12:37
  • 1
    $\begingroup$ Hint 2: It just occurred to me that this is maybe the most simple application of the Pumping lemma imaginable (since "every" string and "every" $i$ works). If you can't apply it here, chances are you have not understood the lemma properly. Revisit the formulation (and our reference material, as linked above). $\endgroup$ – Raphael Jun 9 '15 at 14:16

Suppose that $L$ is CFL then $L$ is regular because it is a unary language. So exist a constant $N$ associated to $L$ by the pumping lemma for regular languages.

We choose the word $\sigma = a^{2^N}$ and $|\sigma| = 2^N > N $ so the pumping lemma should complies for $\sigma$. Then exist a factorization of $\sigma = \alpha \beta \gamma$ such that:

1) $|\alpha \beta|\leq N $

2) $|\beta|\geq 1$

3) $\alpha\beta^i\gamma \in L \forall i \in \mathbb{N}_0$

$|\alpha\beta^i\gamma|= 2^N + |\beta|(i-1)$ choosing $i=2$:

$|\alpha\beta^2\gamma|= 2^N + |\beta|$ so: $$2^N+1\leq|\alpha\beta^2\gamma|\leq 2^N+N$$ $$2^N<2^N+1\leq|\alpha\beta^2\gamma|\leq 2^N+N<2^N +2^N$$ $$2^N<|\alpha\beta^2\gamma|<2^{N+1}$$

Then $|\alpha\beta^2\gamma|$ can't be a power of 2(with natural exponent) so $\alpha\beta^2\gamma\notin L$ and we find a contradiction. Finally $L$ can't be regular and it is not CFL too.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.