My proof of $\{a^p|p~~\mathbb{is~~prime}\}$ is not a CFL.

Question

I want to show that the language $L=\{a^p~|~p~~\mathbb{is~~prime}\}$ is not a CFL.

Assuming towards a contradiction that $L$ is a CFL.

Let $p$ be the number from the Pumping lemma for context-free languages, thus $p$ is a prime.

Choose $w=a^p$, then we can decompose $w=uvxyz$.

So $w_{p+1}=uv^{p+1}xy^{p+1}z$, so $|w_{p+1}|=p+p+p=3p$ which is not a prime number, contradiction.

Is that correct?

Thanks!

Answer 1

The pumping length need not be a prime number. Let $q$ be the pumping length of the language. And let $p$ be any prime number that is greater than the pumping length. Now your argument follows (note that to show that it is not a CFL, you need to have a universal quantification over the subdivision, and not an existential one, so change "we can decompose $w=uvxyz$" to "for any decomposition $w=uvxyz$ of w").

Also as pointed out by @StinkingBishop $|w_{p+1}| = p + |vy|p $.