I'm going over "Introduction to the Theory of Computation" by Michael Sipser in which there's an example of using the pumping lemma for CFLs to prove that $L=\{ a^n b^n c^n \colon n\ge 0 \}$ is not a CFL.

Now, in the book they do it in a way that I understand but I think it can be simplified, so here goes:

Assume by contradiction that $L\in CFL$ with pumping constant $p$ and let $\omega = a^p b^p c^p$. Clearly $\omega \in L$ and $\| \omega \| \ge p$. Let $\omega = uvxyz$ a division such that

  1. $\| vy \| > 0$
  2. $\| vxy \| \le p$

Condition 1 stipulates that for every $i \neq 1$ pumping will actually change the substring $vxy$. Condition 2 stipulates that the substring $vxy$ is comprised of at most two type of alphabet symbols. For now we assume that these symbols are $a$ and $b$.

Combine these two facts and we see that for every $i \neq 1$ the string $uv^i xy^i z$ has a different number of $a$'s and $b$'s than $c$'s.

Again, the proof in the book is a bit more complexed, which leads me to think that I might have a mistake here.

Any thoughts? thanks!

  • 1
    $\begingroup$ What is the question here? Your question does not include a specific question about a specific part of your attempt. Thus, only "yes/no" answers may remain, helping neither you nor future visitors. Please read related meta discussions here and here and adjust your question accordingly, e.g. by formulating a specific question about a single element of your answer you are uncertain about. If you just want general feedback, you are welcome to visit us in Computer Science Chat. $\endgroup$ – Raphael Jul 6 '15 at 9:23

Frankly, I think your argument works. As there is always one of the letters missing, the second condition forces the substring to be "short", pumping will not get equal amounts of $a,b,c$.

For didactical purposes authors in books take extra precautions to make sure the student understands that all cases must be covered. Hence they tend to avoid shortcuts.


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