3
$\begingroup$

A language $L$ is said to have the "no primes" property if:

  1. For every prime $p$ there are no words $w$ in $L$ s.t. $|w|=p$.

  2. For every non-prime $m$ there is at least one word $w\in L$ of length $|w|=m$.

Given a language $L$ that has the no primes property, must $L$ be non-context-free?

Intuitively I believe yes, since the languages of all primes is not context free. But how can I prove this for every language that has this property?

I thiught proving using the sequence of lengths of words from any such language $L$, but this sequence is bounded by (at most) 3 (if 1 is consideres non prime, otherwise bounded by 2).

I also thiught proving by using the pumping lemma, but since I have no information on $L$ I am not sure if its possible.

Is there another method to prove so? Or a counter example that dissproves this?

$\endgroup$
7
$\begingroup$

You can use Parikh's theorem to prove this claim.

Indeed, if such a language was context-free, then its Parikh image would be regular. But the Parikh image would also satisfy the condition (as it only talks about length of words). It's very easy to prove that no regular language can satisfy this condition (e.g. by complementing it and using the pumping lemma).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.