context free language prove or disprove

Question

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.

Answer 1

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.

Answer 2

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