3
$\begingroup$

$L = \left \{ a^{c}\mid \text{c is a composite number} \right \}$
I feel that this is not a context-free language as checking this constraint requires divisibility checking, but I am facing a hard time in proving that $L$ is not a Context Free Language using Pumping Lemma.
Could please anybody please give me a hint?

$\endgroup$
7
$\begingroup$

Let $p$ be the pumping length, and choose a prime $q > p$. The word $a^{q^2}$ is in $L$, and so it can be written as $a^{q^2} = uvwxy$ so that $|vwx| \leq p$, $|vx| \geq 1$, and $uv^iwx^iy \in L$ for all $i \geq 0$. If $|vx| = \ell$ then $1 \leq \ell \leq p$, and for all $i \geq 0$, $q^2 + (i-1)\ell$ is composite. Since $\ell \leq p$ and $q$ is prime, $(q^2,\ell) = 1$, and so Dirichlet's theorem about primes in arithmetic progressions shows that for infinitely many $i \geq 0$, $q^2 + (i-1)\ell$ is prime. We have reached a contradiction.

An easier argument uses Parikh's theorem, which states that a unary language (a subset of $a^*$) is context-free iff it is regular. In particular, it is enough to show that $L$ isn't regular. Since the complement of a regular language is regular, it's enough to show that $\overline{L} = \{ a^k : k \text{ is prime}\}$ is not regular. It is easier to use the pumping lemma for this language. Given a pumping length $p$, choose a prime $q > p$. As before, there must exist $\ell \leq p$ so that $q + (i-1)p$ is prime for all $i \geq 0$. However, for $i = q+1$ we get $q + (i-1)p = q + qp = q(p+1)$, which isn't prime.

$\endgroup$
  • 1
    $\begingroup$ @Yuval loads of thanks to you, specially for saying about Parikh's Theorem. :) $\endgroup$ – Romy Jan 9 '16 at 20:35

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.