3
$\begingroup$

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!

$\endgroup$
  • $\begingroup$ 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.. $\endgroup$ – user2713650 May 30 '15 at 6:05
  • $\begingroup$ 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 $\endgroup$ – user2713650 May 30 '15 at 15:32
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thought so, thanks! $\endgroup$ – user2713650 May 31 '15 at 2:22
  • $\begingroup$ @user2713650: You're welcome! $\endgroup$ – Brian M. Scott May 31 '15 at 8:38

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.