How to prove the language of all binary numbers that are prime is nonregular using pumping lemma?

Question

How to prove the language of all binary numbers that are prime is not regular using pumping lemma?

I have seen Can an infinite set of primes be a regular language or CFG?

We have not studied the CFG so I do not understand that proof. I need a proof by pumping lemma that shows the language of all the prime binary numbers is non-regular.

the pumping lemma says:

that for any regular language $L$

there exists a constant $m$ such that

for any word $w$ in $L$ with length at least $m$

there exits a representation, $w = xyz$ , such that :

1. $length(y)\gt 0$
2. $length(xy) \le m$
3. $xy^iz \in language$ for any $i\ge0$

Answer 1

Suppose that the set of all primes is regular. Then it is recognised by a DFA with say $m$ states. Let $p$ be a prime whose binary expansion ends with $m$ zeros and a $1$, so that $$p=\underbrace{\cdots\ \cdots\ \cdots}_{n\ \rm in\ binary}\, \underbrace{00\cdots00}_{m\ \rm zeros}1=2^{m+1}n+1$$ for some $n$. (We know that there is such a prime from Dirichlet's Theorem.)

The Pumping lemma says that there is a non-empty substring of the $m$ consecutive zeros which can be "pumped". That is, there exists $s$ such that $0<s<m$ and $$\underbrace{\cdots\ \cdots\ \cdots}_{n\ \rm in\ binary}\, \underbrace{00\cdots00\cdots00}_{m+ks\ \rm zeros}1$$ is prime for all $k$. But the number I have just written is $$q=(p-1)2^{ks}+1\ ,$$ that is, $$q=2^{ks}p-(2^{ks}-1)\ .$$ Now choose $k=p-1$. Then by Fermat's little theorem $2^{k}\equiv1\pmod p$, so $p\mid 2^{ks}-1$, so $p\mid q$. That is, $q$ is not prime after all. This is a contradiction, and hence the set of primes is not regular.

---

Here is the version of the Pumping Lemma that I am using. It is more powerful than the one which you have given in your question.

The Pumping Lemma (full version). Suppose that $L$ is a regular language. Then

there exists a constant $m$ such that

for any word $w'ww''$ in $L$ with $length(w)\ge m$ $(*)$

there exist words $x,y,z$ such that

$y$ is not empty, and $w=xyz$, and $w'xy^kzw''$ is in $L$ for every $k\ge0$.

Specifically, the difference is in the line marked $(*)$, which in my version allows us to "pump" not only a string of length at least $m$ which is a word in $L$, but also any string of length at least $m$ which is a subword of some word in $L$. If you have learned the proof of your version of the Pumping Lemma, I think you will be able to see that the same proof holds for the full version, with only very minor changes.

In my answer I have taken $w'$ to be $n$ in binary, $w$ a string of $m$ zeros, and $w''=1$. (And I have written $k+1$ instead of the $k$ in the lemma.)

I do not know if it is possible to prove that the language of primes is not regular using only the simpler version of the Pumping Lemma. My gut feeling is that it would be very difficult, probably impossible.