I have to prove or disprove that for every language $L$ which has the properties:
-
for every non-prime length there is at least one word in L.
-
for every prime length none of the words are in L.
is not a context-free language.
I think it is true and there is no context-free language which has the two properties above but I am stuck.
Best Answer
Hint: Try using the pumping lemma for context-free languages, and Dirichlet's theorem on the infinity of primes in certain arithmetic progressions to prove that the two conditions are inconsistent with $\ L$'s being context-free.
You should be able to show that under the first given condition, if $\ L\ $ were context-free, there would have to exist a word $\ uvwxy \ $, pumpable to $\ uv^nwx^ny\ $ for any positive integer $\ n\ $, in which $\ \vert uvwxy\,\vert\ $ (and hence also $\ \vert uwy\,\vert\ $) is relatively prime to $\ \vert vx\,\vert\ $. It would then follow from Dirichlet's theorem that $\ L\ $ must contain a word of prime length.