0
$\begingroup$

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.

Improve this question
$\endgroup$
6
  • 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
    Commented Jun 9, 2015 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
    Commented Jun 9, 2015 at 11:22
  • 1
    $\begingroup$ See also our reference questions. $\endgroup$
    – Raphael
    Commented Jun 9, 2015 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
    Commented Jun 9, 2015 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
    Commented Jun 9, 2015 at 14:16

1 Answer 1

Reset to default
1
$\begingroup$

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.

Improve this answer
$\endgroup$

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