# Proving that a language is not context-free

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?

Thanks.

• Please show your working so far :) Feb 4 '14 at 12:13
• 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. Feb 4 '14 at 12:30

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.