Automata – How to Prove or Disprove Context Free Languages?

automatacontext-free-grammarpumping-lemma

I have to prove or disprove that for every language $L$ which has the properties:

  1. for every non-prime length there is at least one word in L.

  2. 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.

Related Question