Let $L = \{ab^ncd \mid n \geq 0\}$. If we take $p = 5$ and $w = abbcd$ and write $w_i = xy^iz$, where $x = abb$, $y=c$, $z=d$, then $w_2 = abbccd$ which is not in $L$. We conclude that $L$ is not regular but it obviously is!

What am I doing wrong?


The pumping lemma says that there exists a decomposition of $w$ to $xyz$ such that $y$ can be pumped.

It doesn't say that for all decompositions of $w$ to $xyz$, $y$ can be pumped.

In your example, a possible decomposition is:




  • $\begingroup$ Pumping lemma isn't an iff. It holds for some non regular languages, but always holds for a regular language. $\endgroup$ – jmite Feb 1 '15 at 13:18
  • $\begingroup$ @AswinAlagappan in your example, pumping $y$ even once will give: $aababb$, which is not in $L$. $\endgroup$ – Erel Segal-Halevi Feb 1 '15 at 13:48

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.