0
$\begingroup$

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

If I look at $\bar{L}=\{a^p ~|~ p\text{ is prime}\}$, it is pretty straightforward to show that it is not a CFL with the pumping lemma, by choosing the word $w=a^p$, and with $w_{p+1}=a^{p+sp}=a^{p(1+s)}\notin L$ because $p(1+s)$ is not a prime number.

But what word do I have to choose to prove that $L$ is not a CFL?

Thanks!

$\endgroup$
3

0

Browse other questions tagged or ask your own question.