# Prove the following language is not regular

The set of strings of 0's and 1's, beginning with a 1, such that when interpreted as an integer, that integer is prime.

I'm assuming the best way to move forward is to use the pumping lemma. I'm having difficulty developing a contradiction in this case because typically the membership criteria of the language involves some characteristic of the length of the members (e.g. the members are of length $n$, where $n$ is a perfect square), not their numerical value. Can someone help me apply the pumping lemma in this case?

• When you say interpreted as an integer, do you mean when interpreted as the base two representation of an integer? – Brian M. Scott Nov 4 '13 at 11:42
• The problem is taken directly from Hopcroft's Introduction to Automata Theory. I'm assuming that's what's meant, but please correct me if I'm wrong. – user93189 Nov 4 '13 at 11:53
• It’s a pretty safe bet, if there’s no further explanation. – Brian M. Scott Nov 4 '13 at 11:54

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.
• Can someone explain the math behind $U\cdot 2^{|w|+k|v|} + 2^{|w|}\cdot \frac{2^{k|v|}-1}{2^{|v|}-1}\cdot V+W$ - I think you're converting the binary, pumped number to integer, but I don't understand the math/how it works – maddie Apr 24 '18 at 22:56