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?


1 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.

  • $\begingroup$ Why you've supposed that $p=6$? How does this imply generality? $\endgroup$
    – Mohamad S.
    Commented Apr 8, 2022 at 15:39
  • $\begingroup$ @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. $\endgroup$
    – Arno
    Commented Apr 8, 2022 at 16:45
  • $\begingroup$ @Arno Oh yea I missed it, thanks a lot. $\endgroup$
    – Mohamad S.
    Commented Apr 8, 2022 at 16:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.