Talk:Pumping lemma for regular languages

From Wikipedia, the free encyclopedia

WikiProject Mathematics
Mathematics Portal
This article is within the scope of WikiProject Mathematics, which collaborates on articles related to mathematics.
Mathematics rating: Stub Class Low Priority  Field: Foundations, logic, and set theory
Please update this rating as the article progresses, or if the rating is inaccurate. Please also add comments to suggest improvements to the article.

Contents

[edit] Easy explanation

I added the the Informal statement and explanation section after remembering the frustration I felt when I first tried to understand the pumping lemma. Any input is welcome. I'm not a native English speaker, so I might have messed up at places. Ulfalizer

[edit] TeXify

Any thoughts on TeXifying at least the lemma statement? Might look a little nicer. 141.210.102.198 16:49, 20 April 2007 (UTC)

[edit] Lemma statement

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)

[edit] Example in Lemma Not Sufficient section

The example is rather difficult to follow and actually seems very wrong to me. It needs to prove that for any p > 0, for all strings in the example language, there is a way of dividing it into xyz such that for all integers i ≥ 0, xyiz is also in the example language (where, of course, p i x y z are as in the PL for regular languages). Am I being ignorant or does this need some serious fixes? Citrus538 15:47, 17 December 2006 (UTC)

As far as I see, it needs at least one fix. For short palindromic prefixes uuR we can pump the fisrt letter of the remaining part v (as in the article). However, if the prefix is long we must pump the palindrome. Not only pumping up (which is OK as in the article), but also pumping down (taking k=0). This seems not possible in general. Jochgem 07:43, 13 April 2007 (UTC)

[edit] Unwarranted assumption in first example?

The first example says: "If we let |xy|=p and |z|=p, then xy is the first half of w, or all p of the as". I don't think we can do this - don't we have to consider any case where |xy| ≤ p? The important thing is that y contains at least one a and no bs, which does follow directly from |xy| ≤ p. Dcoetzee 22:14, 14 September 2007 (UTC)

[edit] Philosophy?

Why would this be in the philosophy section? It should be in the computer science / lingustics section. —Preceding unsigned comment added by 24.108.202.22 (talk) 09:05, 19 November 2007 (UTC)