# Proving that if $L=\{ a^n b^n c^n \colon n\ge 0 \}$ than $L\notin CFL$ [closed]

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!

• 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. – 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$.