Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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.

share|improve this question
    
Re: Update: Could you please share the statement you are refering to? –  vonbrand Jan 25 '13 at 14:23
    
@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. –  Stupident Jan 26 '13 at 4:26

2 Answers 2

up vote 4 down vote accepted

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

share|improve this answer

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.

share|improve this answer
    
Thank you for pointing out Dirichlet's theorem. So do you think the argument "PRIME' does satisfy the pumping lemma" is wrong? –  Stupident Jan 23 '13 at 9:59
    
@Stupident, it is wrong, unless you have some weird definition of pumping lemma that does not require a fixed pumping length. –  Karolis Juodelė Jan 23 '13 at 11:33
    
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$. –  Raphael Jan 23 '13 at 13:15
    
@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... –  Karolis Juodelė Jan 23 '13 at 15:02
2  
In a language like this (one symbol only) it is enough to consider lengths, no need to consider chopping up strings and so. –  vonbrand Jan 23 '13 at 19:33

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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