# Show the pumping lemma is not a universal method for proving not context-free

I know that the pumping lemma is not powerful enough to prove a language is not context-free, but I don't understand how to show it.

I have the same question as this one 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, but I couldn't understand the answer in this.

Please explain to me in detail, how can I show $$L = \{ a^i b^j c^k | i ≠ j ≠ k ≠ i \}$$ satisfy the pumping lemma?

Let the pumping length $$p=6$$.

Let $$s=a^ib^jc^k\in L$$, $$|s|\ge p$$.

There are three cases.

• $$i=\max(i,j,k)$$. We will pump a part of $$a^i$$.

$$3i\gt i+j+k=|s|\ge p=6$$. So $$i\ge3$$.

Among three nonnegative numbers $$i-1$$, $$i-2$$ and $$i-3$$, there is one number that is neither $$j$$ nor $$k$$. Suppose it is $$i-d$$ for some $$d\in\{1,2,3\}$$.

$$s=a^{i-d}a^db^jc^k=uvwxy$$, where $$u=a^{i-d}$$, $$v=a^d$$, $$w=x=\epsilon$$, $$y=b^jc^k$$.

• $$|v|=d\ge1$$, $$|vwx|=|v|=d\le3\lt p$$.
• $$uv^0wx^0y = a^{i-d}b^jc^k\in L$$. $$\quad$$(Pumping down is fine.)
• $$uv^nwx^ny = a^{i+(n-1)d}b^jc^k\in L$$ for $$n\gt1$$, since $$i+(n-1)d\gt i$$. $$\quad$$(Pumping up is fine.)
• $$j=\max(i,j,k)$$. We can pump a part of $$b^j$$ just as the case above.

• $$k=\max(i,j,k)$$. We can pump a part of $$c^k$$ just as the cases above.

Hence $$L$$ satisfies the pumping lemma for context-free language with pumping length $$p=6$$.

Exercise. (easy) Show that the pumping lemma for CFLs is not powerful enough to prove $$\{ a^i b^j c^kd^l \mid i,j,k,l\text{ are pairwise distinct} \}$$ is not context-free.

• Why you've supposed that $p=6$? How does this imply generality? Apr 8 at 15:39
• @CSStudent The pumping lemma concludes "there exists a pumping length $p$ such that..". To prove that, you can pick whatever $p$ you want. To disprove that (in order to show that the premise of the language being not CFL) you need to rule out all options.
– Arno
Apr 8 at 16:45
• @Arno Oh yea I missed it, thanks a lot. Apr 8 at 16:48