If you want to make money online : Register now

[Solved]: Pumping Lemma for Regular Language seems to Fail

, , No Comments
Problem Detail: 

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?

Asked By : Aswin Alagappan

Answered By : Erel Segal-Halevi

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:




Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/37838

3.2K people like this

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback