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?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
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$.)

Improve this answer
$\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
    Commented Aug 31, 2021 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.
    Commented Aug 31, 2021 at 16:03
  • $\begingroup$ That's true. Thank you very much, irregardless! $\endgroup$
    – Lightsong
    Commented Aug 31, 2021 at 17:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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