context free language prove or disprove 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.
 A: 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. 
A: Both assertions are wrong. Let $A$ be a nonempty alphabet. 
Take $L = A^*$, which is of course context-free. For each length $n$ (non-prime or not), there is a word of length $n$ in $L$. Thus (1) is satisfied.
Now take $L = \emptyset$, which is also context-free. Then for each length $n$ (prime or not), there is no word of length $n$ in $L$. Thus (2) is satisfied.
EDIT. A language satisfying (1) and (2) simultaneously cannot be context-free. Indeed, let $f:  A^* \to a^*$ be the monoid homomorphism defined by $f(u) = a^{|u|}$ and let $K = f(L)$. By condition (1) and (2), one gets 
$$K = \{a^p \mid \text{$p$ is not prime} \}$$
If $L$ was context-free, then $K$ would be context-free, since context-free languages are closed under homomorphisms. Moreover, a context-free language on a one-letter alphabet is regular (this is a special case of Parikh's theorem). You can now conclude by using the pumping lemma (see this answer for more details).
