I am currently learning the pumping lemma, and encountered the following question, which I am unable to solve:

Prove that $L = \{ 0^n \mid \text{$n$ is power of 2}\}$ is not regular.

I considered $w = 0^{2^n}$, where $n$ is the pumping lemma constant. Then I divided $w$ into $xyz$, where $y \ne \epsilon$ and $|xy| \leq n$. Hence, $|y|$ will be between 1 and $n$. So, $|xy^kz|$ satisfies $L$ if $|y| = 2$ for all values of $k$ and it is within the bound. So, how is $L$ irregular?

The question is to prove it is irregular but here it is coming as regular.

  • 2
    $\begingroup$ The pumping lemma requires $xy^kz$ to be in the language for all values of $k$, not just for some value. $\endgroup$
    – rici
    Commented Aug 21, 2019 at 1:47
  • $\begingroup$ @rici so, if |y| = 2, all values of k will be valid $\endgroup$ Commented Aug 21, 2019 at 2:14
  • 3
    $\begingroup$ All multiples of 2 are not powers of 2. $\endgroup$
    – rici
    Commented Aug 21, 2019 at 4:07
  • 1
    $\begingroup$ Though it's not the case here, some irregular languages satisfy the pumping lemma. $\endgroup$ Commented Aug 21, 2019 at 7:45

1 Answer 1


If you choose $k = 2$ then, writing $|y| = m$, we get $$ xy^2z = 0^{2^n+m}. $$ Since $1 \leq m \leq n$, we have $$ 2^n < 2^n+m \leq 2^n+n. $$ Cantor's theorem shows that $n < 2^n$, and in particular, $$ 2^n < 2^n+m < 2^{n+1}. $$ Therefore $xy^2z \notin L$.

Let me take this opportunity to mention another misconception. There are some non-regular languages which satisfy the pumping lemma. Therefore the fact that you couldn't prove that a certain language is non-regular using the pumping lemma does not imply that the language is regular.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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