1
$\begingroup$

I want to test whether $L= \{w\in\{a,b,c\}^* \mid |w|_a<|w|_b \text{ or } |w|_a<|w|_c,\text{ but not at the same time} \}$ is CFL or not (I assume not), but I am struggling to do so.

The closest I have been to prove that it isn't a CFL is by seeing that the languages $L_1=\{a^nb^{n+1}c^n\mid n\ge0 \}$ and $L_2=\{a^nb^nc^{n+1}\mid n\ge0 \}$, for example, are contained within it and are obviously not context-free, but that doesn't prove anything.

Any tips?

$\endgroup$
1
$\begingroup$

In fact, you have identified a tip!

Let me make it more explicit. Suppose $L$ is context-free and $p>0$ is a pumping length for it as in the pumping lemma for context-free language. Try pumping up or down the word $a^pb^{p+1}c^p$ out of $L$.

(You can also pump up or down the word $a^pb^pc^{p+1}$ out of $L$.)

$\endgroup$
3
  • $\begingroup$ Oh, should the pumping lemma for CFLs be used here? I was actually avoiding that since it was part of a series of recommended problems before showing the pumping lemma, so I suspect this may be solved with CFL closure properties and such $\endgroup$
    – Lightsong
    Aug 31 '21 at 13:26
  • $\begingroup$ I doubt this could be solved without the pumping lemma. The CFL closure properties are not very powerful since CFLs are not closed under intersection nor under union. $\endgroup$
    – John L.
    Aug 31 '21 at 16:03
  • $\begingroup$ That's true. Thank you very much, irregardless! $\endgroup$
    – Lightsong
    Aug 31 '21 at 17:50

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.