# Pumping Lemma for Context Free Languages: Is this language CFL?

I am learning for the first time the Pumping Lemma for CFL, and I thought I understood how it works until I came across this example:

"Show that $L = \{a^m b^m c^n \mid m \leq n\}$ is not a CFL."

My problem is that I find a scenario that the above language can be CFL. I am showing my proof below:

1. Opponent picks $p$
2. We pick $z = a^p b^p c^{2p}$ where $|z| \geq p$
3. Opponent divides the string in $z = uvwxy$ where $|vwx| \leq p$ and $vx$ different than $\epsilon$
4. We have 5 scenarios to consider:
-1- $vwx$ is all $a$'s
-2- $vwx$ is all $b$'s
-3- $vwx$ is all $c$'s
-4- $vwx$ is a combination of $a$'s and $b$'s
-5- $vwx$ is a combination of $b$'s and $c$'s

For scenario -3-, note that if we pump $v$ and $x$, we still get a word that is part of our given language (the number of $c$'s increases, and that does not affect $a$ or $b$). Am I doing something wrong, or is there a flaw in my logic?

• There are some mistakes in the first step. $|z|=3p>p$, and $|vxw|>p$ also. The puming lemma also says that one can take $vwx$ so that $|vw|\leq p$. This means that $vw$ consists only of $a$'s. – zarathustra Nov 9 '14 at 18:11
• My slip, yes |z| >= to p. However, |vwx| <= p and I am not aware of the |vw|≤p. – FranXh Nov 9 '14 at 19:30
• $z=vwx$, they can't be of different length! Maybe you should read the statement of the pumping lemma another time: en.wikipedia.org/wiki/Pumping_lemma_for_regular_languages#/… – zarathustra Nov 9 '14 at 20:29
• @rosebud Could you please explain more clearly what do you meant by "they can't be of different length?". I took the Pumping Lemma from the book I am studying "Automata Theory, Languages, and Computation", and I believe it to be much more accurate than a Wikipedia article. – FranXh Nov 9 '14 at 21:06
• Don't take it the wrong way, I linked wikipedia because it is a free reference. The statement there is actually right, and should match the one in your book. You say $|vwx|\leq p$, but this can't be true since $z=vwx$ and $|z|=4p$. – zarathustra Nov 9 '14 at 22:40