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

Question

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?

Answer 1

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.