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$

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.

  • $\begingroup$ why you have not considered the case where what you are pumping contains the 1 in the end of the string . $\endgroup$ – kiyarash Apr 27 '15 at 4:21
  • $\begingroup$ Because it would be difficult! This part of the Pumping Lemma is a "for all" (universal) statement, so we only need one counterexample to prove that it is false. Clearly I should choose the easiest example I can find. $\endgroup$ – David Apr 27 '15 at 5:05
  • $\begingroup$ The string $xyz$ I have chosen as a counterexample is $0\cdots0$, so there is no possibility that $y$ contains $1$. If you read carefully you will see that I have considered all possibilities. $\endgroup$ – David Apr 27 '15 at 21:24
  • $\begingroup$ Not a big deal either way, the main question is whether they will be useful to future readers. In this case I think probably not. Maybe the first couple of comments would be useful? I have removed some of mine. $\endgroup$ – David Apr 29 '15 at 5:03

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.