Talk:Pumping lemma for regular languages

From Wikipedia, the free encyclopedia

Where is the statement of the lemma? Shouldn't it be front and center?

Good point. It used to be there. I haven't found the edit yet that removed it. Fixed. Jrincayc 04:14, 14 November 2006 (UTC)

[edit] Don't understand how y can be bcbc

I made the change to y so it would be 'bc' rather than 'bcbc' (below) because [so I thought] |xy| must be less than or equal to p. The pumping length appears to be 4 (4 states in the FSA), so if x=a and y=bcbc, |xy|=6 and the language would not be regular. The conditions in Sipser (p.78 2nd ed.) don't seem, IMHO, consistent, but could be read to say y must be at least 'bc'.

"In terms of the pumping lemma, the string abcbcd is broken into a x portion a, a y portion bcbc and a z portion d. (Note, it could be broken in different ways such as a x portion a , a y portion bc and a z portion bcd)"

Yes, you are correct. I will fix the page. Jrincayc 03:24, 6 October 2006 (UTC)