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?

  • $\begingroup$ When you say interpreted as an integer, do you mean when interpreted as the base two representation of an integer? $\endgroup$ – Brian M. Scott Nov 4 '13 at 11:42
  • $\begingroup$ 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. $\endgroup$ – user93189 Nov 4 '13 at 11:53
  • $\begingroup$ It’s a pretty safe bet, if there’s no further explanation. $\endgroup$ – 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.

  • $\begingroup$ 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 $\endgroup$ – maddie Apr 24 '18 at 22:56

Your Answer

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

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