# Show that the Pumping Lemma for CFLs is not powerful enough to prove that the language L = {aibjck |i ≠j ≠ k ≠ i } is not context free

Show that the Pumping Lemma for CFLs is not powerful enough to prove that the language $L = \{a^ib^jc^k \mid i ≠j ≠ k ≠ i \}$ is not context free.

From my understanding, we want to prove that all 3 conditions of the pumping lemma hold. This will not guarantee that the language is context-free. However, I have found a case where it breaks

Let the string be $abbccc$

If $u = \lambda$, $v = a$, $x = aa$, $y = a$, $z = bbccc$.

Therefore, when we pump the string for $i = 2$, we get $aaaaaabbcccccc$, which is NOT in the language because we have the same number of $a$'s and $c$'s. How is this possible?

• Have you tried w = bcc. The professor hinted to find a w such that it is not pumpable. Mar 22, 2018 at 0:23
• Welcome to Computer Science! Note that you can use LaTeX here to typeset mathematics in a more readable way. See here for a short introduction.
– Raphael
Mar 22, 2018 at 9:29

## 1 Answer

The Pumping Lemma states: "... there exists a constant $p$ such that for each word $w\in L$ with $|w|\ge p$ there exists a decomposition $w = uvxyz$ such that ...", where $p$ is the pumping constant.

You have chosen your own decomposition, and shown it not fit the pumping property. Perhaps there is another decomposition that will work?

And even in the case your example would work, I can claim that the pumping is larger than 6.