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.

  • $\begingroup$ Re: Update: Could you please share the statement you are refering to? $\endgroup$
    – vonbrand
    Commented Jan 25, 2013 at 14:23
  • $\begingroup$ @vonbrand, I don't have the book at hand, but you may refer to A note on the Pumping Lemma for regular languages, where the Version I and II of the Pumping Lemma are just those two forms mentioned above. $\endgroup$
    – Stupident
    Commented Jan 26, 2013 at 4:26
  • $\begingroup$ See also cs.stackexchange.com/q/4984/755 $\endgroup$
    – D.W.
    Commented Dec 18, 2015 at 18:39

2 Answers 2


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


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.

  • $\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
    Commented Jan 23, 2013 at 9:59
  • 1
    $\begingroup$ @Stupident, it is wrong, unless you have some weird definition of pumping lemma that does not require a fixed pumping length. $\endgroup$ Commented Jan 23, 2013 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
    Commented Jan 23, 2013 at 13:15
  • 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
    Commented Jan 23, 2013 at 19:33
  • 1
    $\begingroup$ Karolis, after some thinking I agreed but thought the argument was too fast to follow (esp for beginners) so I added a more elaborate answer. $\endgroup$
    – Raphael
    Commented Jan 24, 2013 at 7:04

Your Answer

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

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