I've faced this question while I was solving some past homework and I couldn't really figure out how I would solve it.

Question: Prove that $L=\{a^ib^jc^k\ |\ i\neq j,\ i\neq k,\ j\neq k\}$ satisfies the pumping lemma even though it's not a CFL.

Note: There's no need to prove that it's not a CFL.

The purpose of the question is to show that the pumping lemma is a necessary condition for a language being CFL but isn't enough to determine whether it's a CFL or not.

I have an idea to prove it but I couldn't write a formal and proper proof for it.

  • $\begingroup$ Oh, yea thanks it does. $\endgroup$
    – Mohamad S.
    Apr 8, 2022 at 15:01


Browse other questions tagged or ask your own question.