# Pumping Lemma for CGF question

I'm going through a pumping lemma for a proof that: the language $B = \{a^nb^nc^n \mid n\ge 0\}$ is not context free

The first case considers when both v and y contain only one type of alphabet symbol causing a contradiction which I understand.

The second case considered when either v or y contain two alphabet symbols which i also i understand but they conclude that: $uv^2xy^2z$ may contain equal numbers of the three alphabet symbols but not in the correct order - I don't see how this is possible? Could someone provide an example of what the author is referring to here?

Thanks a lot!

• Ironically I've found a slide with the same example stating:"pumping will change the number of some letters in s, but not all. So pumping will lead s out of B." yet the author has stated its possible to get equal numbers of all alphabetical symbols but not in the correct order. Hmm.. – user2713650 May 30 '15 at 6:05
• Ok so I see you can get the alphabetical symbols in the incorrect order (e.g. if we split v= ab and ab^2 will just be v concatenated onto itself twice: abab (thus in the incorrect order), but there's no way we can have the same number of alphabet symbols is there? because v and y will always at most contain 2 letters in any possible way we try to split a^pb^pc^p – user2713650 May 30 '15 at 15:32

You are correct, assuming that you start with the word $s=a^pb^pc^p$, where $p$ is the pumping length. If you decompose $s$ as $s=uvxyz$ in such a way that $|vxy|\le p$ and $|vy|\ge 1$, then clearly the string $vxy$ must lie entirely within $a^pb^p$ or entirely within $b^pc^p$, since any substring that contains both an $a$ and a $c$ must contain at least $p+2$ characters. Thus, pumping must leave at least one of of the substrings $a^p$ and $c^p$ of $s$ must be unaffected by pumping, and for $k\ne 1$ it is impossible for $uv^kxy^kz$ to have the same numbers of $a$s, $b$s, and $c$s: at most two of these numbers can be the same.