Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?


share|cite|improve this question
up vote 1 down vote accepted

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.

share|cite|improve this answer

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

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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