# context free language prove or disprove

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.

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.

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

• I took the qestion to be whether a language that has both properties can be context-free. I don't believe it can, for the reasons suggested in my answer. – lonza leggiera Feb 10 at 13:14
• @lonzaleggiera Thank you for your remark. I edited my answer to treat this case as well. – J.-E. Pin Feb 10 at 18:56
• Under the two conditions shouldn't $\ K\$ be $\ \{ a^c\,\vert\, c \ge 0,\ \mbox{ not prime }\,\}\$. Although the statements of the conditions aren't entirely clear, I read the first as saying that $\ L\$ contains a word of every non-prime length, and the second as saying that it contains no words of any prime length. I think your proof still works, but I think it needs to be shown that you can choose a pumpable word that will pump out one of prime length, which doesn't seem to me to be an entirely trivial observation. – lonza leggiera Feb 11 at 7:35
• Thanks again. You are perfectly right, it is "not prime". For the second part of you comment, isn't it what is done in the linked answer? – J.-E. Pin Feb 11 at 9:55
• Yes, apologies for not looking carefully enough at the linked example. While it doesn't do what I suggested, the method it does use is an easier way of arriving at the end result, thus showing that what I suggested was not necessary. – lonza leggiera Feb 11 at 10:13