I'm not very comfortable with pumping lemma for context-free grammar. I understand the sufficient conditions that must hold but proving it gets me everytime. For example, I need to prove whether $L=\{0^{2^n}∣n \geq 0\}$ is not context-free.

There is no pattern of 0's that can be recreated by a pushdown automata but alas I need to prove this. I know you start off assuming it is by being able to create a substring $uvxyz$ where $v$ and $y$ are raised to the $i$th power where $i≥0$. I'm having trouble from there, any help in this and the understanding would be greatly appreciated.

  • 1
    $\begingroup$ See meta.cs.stackexchange.com/questions/599 and more specifically cs.stackexchange.com/questions/265/… $\endgroup$
    – babou
    Apr 13, 2015 at 15:53
  • $\begingroup$ Maybe you should go back to the statement of a lemma, it says that, if the language is CF, then there is a number $p$ such that, if a sentence is longer than $p$ then ...it can be decomposed so that ... and that gives you a set of other strings that must be in the language ... but for some reason (that may vary) sme of these strings cannot be ... so the language is not CF. $\endgroup$
    – babou
    Apr 13, 2015 at 16:02

1 Answer 1


A unary language (a language over a unary alphabet) is context-free if and only if it is regular. The easiest way to see this is to convert a context-free grammar to a regular grammar using the fact that $xy = yx$ over a unary alphabet.

There are many ways of showing that $L$ is not regular, and so not context-free. One way is using the Myhill–Nerode criterion. Since $0^{2^n} 0^{2^n} \in L$ while $0^{2^m} 0^{2^n} \notin L$ for $m \neq n$, we see that the words $\{ 0^{2^n} : n \geq 0 \}$ are pairwise inequivalent, and so $L$ is not regular.

A proof using the pumping lemma is also not too difficult. Given a pumping length $n$, choose $m$ so that $2^{m-1} > n$, and consider the word $0^{2^m} \in L$. According to the pumping lemma you can write $0^{2^m} = xyz$ with $|xy| \leq n < 2^{m-1}$ and $|y| \geq 1$ so that $xz \in L$. But $xz = 0^{2^m-|y|}$ cannot be in $L$ since $2^{m-1} < 2^m-|y| < 2^m$. This contradiction shows that $L$ is not regular.


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