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 Aug 21 '19 at 1:47
  • $\begingroup$ @rici so, if |y| = 2, all values of k will be valid $\endgroup$ – Shantanu Shinde Aug 21 '19 at 2:14
  • 2
    $\begingroup$ All multiples of 2 are not powers of 2. $\endgroup$ – rici Aug 21 '19 at 4:07
  • 1
    $\begingroup$ Though it's not the case here, some irregular languages satisfy the pumping lemma. $\endgroup$ – Yuval Filmus Aug 21 '19 at 7:45

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, privacy policy and cookie policy

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