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| &gt; 0$ and $|vxy| \leq m$.  These are:

$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.

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 &gt; m$.
So my question is essentially, is this a valid proof and if not what is wrong with it?
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.