2
$\begingroup$

In the section of my textbook covering the pumping lemma, there are practice questions asking us to prove a given language is not regular.

I have not been able to solve this one:

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

My attempt:

Assume to the contrary that the language is regular. Let $p$ be the pumping length given by the pumping lemma. Let $s = 101$. The pumping lemma guarantees s can be broken into 3 substrings, x, y, z such that $|xy| \leq p$ and $y \neq \epsilon$....

Obviously this is where it breaks down, because I haven't given a string that is of at least length $p$ (ie $s = 10^p1$).

$\endgroup$
  • 1
    $\begingroup$ Crosspost on math.SE -- please don't do that. It's rude on people that waste their time on writing redundant answer.s $\endgroup$ – Raphael May 3 '18 at 22:57
2
$\begingroup$

I believe what you are missing is Fermat's Little Theorem: If $p$ is a prime and $p$ does not divide $a$, then $a^{p-1}\equiv 1 \mod p$.

I'll give an example application in base 10. Let's assume that 2039 is the prime to which the pumping lemma is applied and the decomposition is 2 03 9. That is the pumping lemma would imply that all strings of the form $2(03)^n9$ denote prime numbers. At least it is true for $n\in\{0,1,2\}$. But without further calculation I know that it fails for $n=28$: The number $N=2030303030303030303030303030303030303030303030303030303039$ is divisible by $29$, which is the number at $n=0$. To see this, observe that $N = 20\cdot 100^{28} + \sum\limits_{0\leq i< 28}30\cdot 100^i + 9 = 20\cdot 100^{28} + 30\cdot\frac{100^{28}-1}{100-1} + 9$ and apply Fermat's theorem. Here, we also use that $29$ does not divide $100-1$.

I hope from this you are able to solve the exercise.

$\endgroup$
1
$\begingroup$

One way to show that this language isn’t regular is to use the following theorem:

Let $L$ be a regular language over $\Sigma$, and let $c_n = |L \cap \Sigma^n|$. There exists a modulus $m \geq 1$ such that for all $0 \leq r < m$ there exist real $C,\lambda \geq 0$ and integer $k \geq 0$ such that the following asymptotic estimate holds for $n \equiv r \pmod{m}$: $$ c_n \sim Cn^k \lambda^n. $$

In your case, $c_n$ is the number of primes between $2^{n-1}$ and $2^n-1$. According to the prime number theorem, the number of primes up to $2^n$ is asymptotic to $2^n/n \log 2$, and so $$ c_n \sim \frac{1}{\log 2} \left( \frac{2^n}{n} - \frac{2^{n-1}}{n-1} \right) \sim \frac{1}{2\log 2} \frac{2^n}{n}. $$ This contradicts the theorem above.

$\endgroup$
  • $\begingroup$ Would you mind giving me a reference for this theorem, @Yuval Filmus ? $\endgroup$ – Peter Leupold May 4 '18 at 9:43
  • 1
    $\begingroup$ See Wikipedia, which cites Theorem V.3 of Flajolet and Sedgewick. $\endgroup$ – Yuval Filmus May 4 '18 at 10:43

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.