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:

$x=a$

$y=bb$

$z=cd$

Best Answer from StackOverflow

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

3.2K people like this

 Download Related Notes/Documents

0 comments:

Post a Comment

Let us know your responses and feedback