I'm currently stuck on a homework problem, and I feel completely lost about how to solve it. Generally I find pumping lemma proofs to be pretty straight-forward, but I feel like I'm missing something for this one.

The language I need to prove is not context-free is: $L = \{a^ib^jc^k | i \neq j, i \neq k, j \neq k\}$

So I understand the basic idea of what I need to do: find a string which I can split into sub-strings u,v,w,x,and y such that no matter where I place v and x, they can be pumped to make $i=j$ or $i=k$ or $j=k$.

My strategy I was using was to make i, j, and k different multiples of p (the pumping length). But the problem is that v or x can be any length from 1 to p, and I can't come up with any length for i,j, or k so that all those potential lengths of v/x can be pumped to make i or j or k equal.

I feel like I am overthinking this problem or am overlooking some property of the pumping lemma that will help me.

I am NOT looking for the answer, but rather just some guidance on how to think about this problem, as I think my current strategy is impossible.

  • $\begingroup$ Do you know Ogden's Lemma? According to an answer by Yuval your language will withstand the classical pumping lemma. Another answer by Janoma explains how to use Ogden's lemma, but unfortunately exactly on your language- so don't look there. But even when familiar with Ogden the trick is nasty and involves choosing a word with factorials. $\endgroup$ Dec 6 '20 at 5:21

Your Answer

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

Browse other questions tagged or ask your own question.