1
$\begingroup$

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?

$\endgroup$

1 Answer 1

2
$\begingroup$

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.

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

Your Answer

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

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