Proving $\{0^{2^n}\}$ is not regular using pumping lemma

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.

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

1 Answer

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.