Problem Detail: 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 }$
- Prove that $mathrm{PRIME}’$ is non-regular.
- 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:
- We pick $m$ s.t. $m geq 4$.
- 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.
Asked By : Stupident
Answered By : Raphael
Let $w in mathrm{PRIME}’$ with $|w| geq 5$. Distinguish two cases.
- $|w|$ is even — in that case, choose $x = varepsilon$, $y = aa$ and $z = a^{|w|-2}$. Then, for all $igeq 0$, we have $|xy^iz|$ is even and greater than two, as $|z| geq 3$, and therefore not prime; $xy^iz in mathrm{PRIME}’$.
- $|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 $pgeq m$ prime. Assume there was a $1<kleq m$ so that some $1<dleq 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$.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/9104
