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?

  • $\begingroup$ 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. $\endgroup$ – zarathustra Nov 9 '14 at 18:11
  • $\begingroup$ My slip, yes |z| >= to p. However, |vwx| <= p and I am not aware of the |vw|≤p. $\endgroup$ – FranXh Nov 9 '14 at 19:30
  • $\begingroup$ $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#/… $\endgroup$ – zarathustra Nov 9 '14 at 20:29
  • $\begingroup$ @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. $\endgroup$ – FranXh Nov 9 '14 at 21:06
  • $\begingroup$ 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$. $\endgroup$ – zarathustra Nov 9 '14 at 22:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.