I am trying to use the pumping lemma to prove that the language consisting of the set of $0$'s and $1$'s, beginning with a $1$, such that when interpreted as an integer, that integer is prime, is not regular.

This post has an accepted solution

Pumping lemma is the key. If the language were regular, thered be strings $u,v,w$ such that $uv^*w\subseteq L$ and $|v|>0$ and wlog $|u|>0$, i.e. $u\in 1\{0,1\}^*$ If $U,V,W$ are the numbers represented by $u,v,w$ (where $v,w$ may have leading zeroes), then the number represented by $uv^kw$ is $U\cdot 2^{|w|+k|v|} + 2^{|w|}\cdot > \frac{2^{k|v|}-1}{2^{|v|}-1}\cdot V+W$, where $U\ge 1$. Show that these cannot all be prime.

From what I understand, you break the binary string into $U,V$ and $W$. The pumping lemma says that for a regular language, for every $i >= 0$, $UV^iW \in L$. You simply then choose an i and show that $UV^iW$ is not a member of the language.

However, I don't understand why it works that you can represent the number as $U\cdot 2^{|w|+k|v|} + 2^{|w|}\cdot \frac{2^{k|v|}-1}{2^{|v|}-1}\cdot V+W$, where $U\ge 1$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.