[Solved]: Pumping Lemma for $L = \left \{ a^{c}\mid \text{c is a composite number} \right \}$

Problem Detail: 

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

Asked By : Romy

Answered By : Yuval Filmus

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/51671

 Ask a Question

 Download Related Notes/Documents