Prove the following language is not regular

Question

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 04 '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 04 '13 at 11:53
It’s a pretty safe bet, if there’s no further explanation. — Brian M. Scott, Nov 04 '13 at 11:54
Possible duplicate of Prove that the language ${bin(p) \mid p\ \text{is prime}}$ is not regular (prime numbers) — Chain Markov, Nov 27 '19 at 19:03

score 3 · Accepted Answer · answered Nov 04 '13 at 11:43

3

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.

answered Nov 04 '13 at 11:43

Hagen von Eitzen

374,180

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

Prove the following language is not regular

1 Answers1

Linked