4
$\begingroup$

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?

$\endgroup$
2
  • 1
    $\begingroup$ See answers of this question for general remarks on how to use the Pumping lemma. $\endgroup$
    – Raphael
    Apr 22, 2012 at 21:44
  • 1
    $\begingroup$ 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? $\endgroup$
    – yo'
    May 3, 2012 at 18:39

4 Answers 4

9
$\begingroup$

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.

$\endgroup$
7
  • 3
    $\begingroup$ 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. $\endgroup$
    – Raphael
    Apr 22, 2012 at 21:48
  • 1
    $\begingroup$ @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. $\endgroup$ Apr 22, 2012 at 21:50
  • 1
    $\begingroup$ 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. $\endgroup$
    – Raphael
    Apr 22, 2012 at 22:11
  • $\begingroup$ @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. $\endgroup$ Apr 22, 2012 at 22:15
  • 1
    $\begingroup$ @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. $\endgroup$
    – vonbrand
    Jan 30, 2013 at 20:24
4
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.