3
$\begingroup$

Here is a question from Daniel I. A. Cohen's book Introduction to Computer Theory:

Consider the language:

$\quad \mathrm{PRIME}' = \{ a^n \mid n \text{ is not a prime} \} = \{ \varepsilon, a, aaaa, aaaaaa, aaaaaaaa, \ldots \}$

  1. Prove that $\mathrm{PRIME}'$ is non-regular.
  2. Prove, however, that $\mathrm{PRIME}'$ does satisfy the pumping lemma.

Part 1. is really easy to prove. I start my proof of part 2. like this:

  1. We pick $m$ s.t. $m \geq 4$.
  2. The opponent picks $w = a^{n^2}$, where $n$ is any prime number greater than m.

Now I don't know how to decompose $w$ into $xyz$. Any help would be appreciated.


Update: According to the answers below, $\mathrm{PRIME}'$ doesn't satisfy the Pumping Lemma we commonly talk about (requiring $|xy| \leq m$). I have checked the book at the library and found there are two versions of the Pumping Lemma in it. The weaker one, which clearly this question refers to, doesn't require a fixed pumping length.

$\endgroup$
4
$\begingroup$

Let $w \in \mathrm{PRIME}'$ with $|w| \geq 5$. Distinguish two cases.

  1. $|w|$ is even -- in that case, choose $x = \varepsilon$, $y = aa$ and $z = a^{|w|-2}$. Then, for all $i\geq 0$, we have $|xy^iz|$ is even and greater than two, as $|z| \geq 3$, and therefore not prime; $xy^iz \in \mathrm{PRIME}'$.

  2. $|w|$ is odd -- in this case, we can not verify the pumping property. This can be seen as follows.

    We have

    $\quad \forall m \geq 1.\, \exists n \geq m.\, \forall 1 < k \leq m.\, \gcd(k, n-k) = 1 \qquad (\star)$

    that is for every assumed pumping length $m$, there is a longer word $a^n$ which you can not separate into $a^k$ and $a^{n-k}$ with $k \leq m$ (note that $k=1$ trivially violates the pumping property) so that $k$ and $n-k$ share a divisor. Therefore, we can invoke Dirichlet's theorem for every possible separation, which yields that there are (infinitely many) primes you get by $(n-k) + ik$. So we can't find a pumpable split of $a^n$, and thus the pumping property is violated for $a^n$, which is enough to "contradict" the lemma.

    $(\star)$ can be shown by contradiction. Pick $n>m$ non-prime so that $n$ has no prime factor $\leq m$, e.g. $n = p^2$ for $p\geq m$ prime. Assume there was a $1<k\leq m$ so that some $1<d\leq k$ divided both $k$ and $n-k$, i.e. $k = id$ and $n-k = jd$ for some natural $i,j$. But then, $n = (i+j)d$, i.e. $d \leq m$ divides $n$, which contradicts the choice of $n$.

$\endgroup$
3
$\begingroup$

Pick $xyz$ so that $|y|$ is not coprime to $|xyz|$. This does not work when $|xyz|$ does not have prime factors smaller than the pumping length though. In that case there will be a prime amongst all $|xy^nz|$ by Dirichlet's theorem.

$\endgroup$
  • $\begingroup$ Thank you for pointing out Dirichlet's theorem. So do you think the argument "PRIME' does satisfy the pumping lemma" is wrong? $\endgroup$ – Stupident Jan 23 '13 at 9:59
  • $\begingroup$ @Stupident, it is wrong, unless you have some weird definition of pumping lemma that does not require a fixed pumping length. $\endgroup$ – Karolis Juodelė Jan 23 '13 at 11:33
  • $\begingroup$ In order to apply the theorem to the effect you state, you need for every $p > 0$ an $n \leq p$ such that for all $k \leq p$, $k$ and $n-k$ are coprime (in particular, not $k$ and $n$ as you claim). It is not clear to me how you pick $n$. $\endgroup$ – Raphael Jan 23 '13 at 13:15
  • $\begingroup$ @Raphael, note that $\text{gcd}(k, n) = \text{gcd}(k, n-k)$. I'm unsure what your variables mean ($p$ the pumping length, $n = |xyz|$ and $k = |y|$?). Regardless, I don't think I missed anything in my answer... $\endgroup$ – Karolis Juodelė Jan 23 '13 at 15:02
  • 2
    $\begingroup$ In a language like this (one symbol only) it is enough to consider lengths, no need to consider chopping up strings and so. $\endgroup$ – vonbrand Jan 23 '13 at 19:33

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.