# Pumping Lemma for Regular Language seems to Fail

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:

$x=a$

$y=bb$

$z=cd$

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