# Prime number CFG and Pumping Lemma

So I have a problem that I'm looking over for an exam that is coming up in my Theory of Computation class. I've had a lot of problems with the pumping lemma, so I was wondering if I might be able to get a comment on what I believe is a valid proof to this problem. From what I have seen online and in our review I don't think this is the customary answer to this problem so I want to know if I am applying the concepts behind the pumping lemma successfully. The problem is not a homework problem and can be found on my professor's previous exams here under the fourth problem of his exam given in Fall of 2011, which is...

Let $L = \{0^p \mid \text{$$p$$ is a prime number}\}$. Prove that $L$ is not context-free using the pumping lemma for context-free languages.

So here is my proof:

Assume that the pumping length is $m$, where $m+1$ is a prime number. I shall also assume that there is a string $uvxyz = 0^{(m/2)}00^{m/2} \in L$. There are two possible positions that do not violate conditions 2 and 3 of the pumping lemma for context languages, being $|vy| > 0$ and $|vxy| \leq m$. These are:

1. $u = 0^{(m/2)}, v = 0, x = 0^{m/2}$, pumping by one results in $0^{m/2}000^{m/2}$. Since m/2 + m/2 is m, which is one less than the prime number m+1, it is an even number. m+2 is also an even number and since $|0^{m/2}000^{m/2}| = m + 2$, this number of zeroes is also even and thus cannot be prime, resulting in a contradiction.

2. The other placement is to place the string on the symmetric opposite or $x = 0^{m/2}, y = 0, z = 0^{m/2}$. This results in the same contraction as in case 1.

The string cannot be placed in the center such that $v = 0^{m/2}, x = 0, y = 0^{m/2}$ as this would violate condition three or $|vxy| \leq m$, since $|vxy| = m + 1 > m$.

So my question is essentially, is this a valid proof and if not what is wrong with it?

• See answers of this question for general remarks on how to use the Pumping lemma. – Raphael Apr 22 '12 at 21:44
• Cannot you simply say that no arithmetic progression of the form $0^{km+l}$ where $m$ is the pumping length, $l$ is the minimal word length that can be pumped and $k\in\mathbb N$ cannot comprise only primes? – yo' May 3 '12 at 18:39

Your proof is incomplete, there are many cases you don't cover. You are not ruling out, for example, $u = 0^{m/2-3}$, $v=0$, $x=00$, $y=00$, $z=0^{m/2-2}$.

A good hint that your proof is wrong is that all you're using about prime numbers is that they're odd¹. Odd numbers do form a context-free language.

The pumping lemma gives you $uvxyz=0^p \in L$ and for all $n\in\mathbb{N}$, $uv^nxy^nz = 0^{p+(n-1)k} \in L$, with $k = |vy| \ge 1$. Now you need to prove that the numbers $\{p + (n-1)k \mid n\in\mathbb{N}\}$ cannot all be prime.

Look at the values of $p + (n-1)k$ modulo $k+1$ when $n$ varies from $1$ to $k+1$. Since $k$ and $k+1$ are co-prime, one of them has to be $0$ modulo $k+1$, meaning that it is a multiple of $k+1$ (and not $k+1$ itself because it's larger), so it is not prime. Depending on your mathematics background, you may formulate this argument using the Chinese remainder theorem or any other equivalent theorem.

¹ And you didn't account for $2$ being prime, but that's ok, it's enough to consider sufficiently long words, because the status of a finite number of words doesn't affect the context-freedom of the language.

• You might want to add that $m$ is not chosen correctly; why would the pumping constant have the desired form? With $p$ the pumping constant, choose $m \geq p$ with $m+1$ prime (provided such $m$ works out, I did not check). Of course all such $m$ are alternative pumping constants; just being pendantic. – Raphael Apr 22 '12 at 21:48
• @Raphael All that's needed for that step is to know that whatever the pumping constant is, there is a larger prime. That's a well-known result. – Gilles 'SO- stop being evil' Apr 22 '12 at 21:50
• Sure, but it is a step, isn't it? The proposed solution (by OP) is close to "I choose the pumping constant as I need it" which would be wrong. Therefore I think it is useful to spell this step out clearly so there can be no confusion. – Raphael Apr 22 '12 at 22:11
• @Raphael No, this is just a wording quibble. $m$ is not really the pumping length, it's an integer larger than the pumping length. But I'd let it go if I was grading. – Gilles 'SO- stop being evil' Apr 22 '12 at 22:15
• @Gilles, all that is needed is that there is a prime larger than $m$, but the "proof" states that $m + 1$ is prime, and that just can't be taken for granted. – vonbrand Jan 30 '13 at 20:24

If $L$ is context-free, then by Parikh's theorem, the set $\{p \mid \text{$p$is a prime number}\}$ is a finite union of arithmetic progressions. Therefore, there exists an infinite arithmetic progression $a, a+r, a+2r, \dotsm$ consisting only of prime numbers. In particular $a$ should be prime, but then $a + ar = a(r+1)$ is not prime. Contradiction.

If you know the result that any CFL over a 1-symbol alphabet is regular, then you just have to show that the language isn't regular, which is a trifle easier than showing that it's not a CFL.

Use the pumping lemma for context free languages, and argue by contradiction. Say the constant of the lemma is $n$, and let $p$ be a prime $p \ge n$. If the language is context free, the string $a^p$ can be written:

$a^p = u v x y z$

where $0 < \lvert v y \rvert < n$, such that for all $k \ge 0$ the string $x v^k x y^k z$ represents a prime. If we call $\lvert v y \rvert = l$, this means $p + (k - 1) l$ is a prime for all $k$. Pick $k = p + 1$, and you conclude that $p + p l = p (l + 1)$ is prime. But $l \ge 1$, so $l + 1 \ne 1$, a contradiction.