Given the language $$L = \{ a^p \mid p\, \text{IS NOT prime} \}$$ is $L$ Context free? If not, prove that it's not.

May I have some suggestions on how to use the pumping lemma to prove this, please?


  • 1
    $\begingroup$ Please show your working so far :) $\endgroup$
    – Shaun
    Feb 4 '14 at 12:13
  • $\begingroup$ I suggest using the pumping lemma to derive a contradiction. That's the way pumping lemmas are typically used to prove that languages don't fall into the relevant class. $\endgroup$ Feb 4 '14 at 12:30

I don't know if you were asked to use necessarily the pumping lemma in order to solve the problem, but in this case of language, it is much easier to use Parikh's theorem.

The alphabet of the language is $\Sigma=\{a\}$. So, for every word $w$, Parikh's vector is $P(w)=|w|_{a}$ (which is the number of occurences of $a$ in $w$). Then, the set of Parikh's vectors for language $L$ of the exercise is the set of divisible numbers. $$S=\{P(w):w\in L\}=\{|a^p|: p~\text{not prime}\}=\{p:p~\text{not prime}\}$$

It is easy to show that this set is not semi-linear, since no finite union of linear sets can result to $S$. If there was such a union, a divisible number would be missing, leading to contradiction.


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.