How to prove that the following language is not regular?

Question

This is the following problem that I've been having difficulty on:

For this problem, we will show that there are non-regular languages over the alphabet $\{0\}$. The language that will be used is the following:

$$P_2 = \left\{0^{2^k}\mid k\ge 0\right\} = \{0, 00, 0000, \dots\}$$

This language contains all the strings of the form $0^\ell$, where $\ell$ is the power of two. Show that this language is not regular.

My question is, how would I approach this problem to go about solving it?

Thanks!

Answer 1

Use the pumping lemma. Assume your language is regular, and let $N$ be the pumping lemma constant. Take $\sigma = 0^{2^m}$ in the language, where $m = \max(3, N)$, it's length is greater than $N$. So we can write $\sigma = \alpha \beta \gamma$, with $\beta \ne \epsilon$, length of $\beta$ (call it $b$) less than $N$, such that $\alpha \beta^k \gamma$ belongs to the language for all $k$. Consider $\alpha \beta^2 \gamma$, it's length is $2^m + b \le 2^m + N < 2^{m + 1}$. As the resulting length isn't a power of 2, $\alpha \beta^2 \gamma$ isn't part of the language, contadicting the pumping lemma. So the language isn't regular.

Answer 2

HINT: Use the pumping lemma for regular languages; the non-regularity of your language is an easy consequence of it.