Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question

2 Answers 2

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|improve this answer

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

share|improve this answer

Your Answer

 
discard

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.