2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – lonza leggiera Feb 10 at 13:14
  • $\begingroup$ @lonzaleggiera Thank you for your remark. I edited my answer to treat this case as well. $\endgroup$ – J.-E. Pin Feb 10 at 18:56
  • $\begingroup$ 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. $\endgroup$ – lonza leggiera Feb 11 at 7:35
  • $\begingroup$ 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? $\endgroup$ – J.-E. Pin Feb 11 at 9:55
  • $\begingroup$ 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. $\endgroup$ – lonza leggiera Feb 11 at 10:13

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.