Talk:Pumping lemma

Untitled[edit]

In the theory of formal languages, the pumping lemmas provide necessary conditions for languages to be [[regular language|regular]] or context-free. They are almost exclusively used in order to prove that a given language is not regular or context-free.

I found this rather short on explanation of the name.

One can say therefore that 'pumping lemma' is a name for the application of the pigeonhole principle, in the context of a finite state machine.

I know the pigeonhole principle and it is not clear that this is an application of it. If I did not know the principle, it would certainly not be helpful to read about it if I wanted to understand the pumping lemmas. Better to just get on with it. Maybe this could be a comment after the proof.

The Hebrew Interwiki in this article[edit]

Please note that the Hebrew interwiki is to an article concerning the "Pumping lemma for context-free languages", not a general article regarding pumping lemmas. 80.178.196.196 09:05, 27 August 2005 (UTC)[reply]

CFG version notation confusion[edit]

There are two i's, one for a^ib^ic^i, and the other for v^ixy^i. This creates unnecessary confusion.

Disambiguation?[edit]

It seems there is a separate page on the pumping lemma for regular languages. Perhaps Pumping Lemma should contain a general definition, with links to pages on the pumping lemma for regular languages and for context free languages?

Context?[edit]

The intro needs to provide more context for nonspecialists. I presume this does not apply to human languages, but rather only to computer languages? If so, this should be stated clearly. If not, the introduction needs to be made clearer.--Srleffler 05:28, 13 December 2006 (UTC)[reply]

I added another link to computability theory. The link to formal languages also gives context. CMummert 03:04, 17 December 2006 (UTC)[reply]

Finite languages[edit]

I'm new to this topic, so let me know if I'm missing something. Currently there are a few interesting but irrelevant sentences about pumping lemmas for finite languages.

The actual situation surely is that any finite language vacuously has a pumping lemma since there aren't any strings beyond a certain length, and so we can just choose a pumping length greater than the length of the longest word. Alternatively, we could just note that any finite language is regular, and so has a pumping lemma. Thus, as the person who added the "Correction:" section (though surely they should've corrected the text itself rather than just being lazy!) correctly noted, the claim in the first paragraph that "if there is a pumping lemma for a given language class, any nonempty language in the class will contain an infinite set of finite strings" is wrong. However, the second paragraph in "Correction:" is missing the point. It's true that for non-context free AND non-regular languages, a pumping lemma implies (non-trivial) languages are infinite, but only vacuously, since there are no non-regular finite languages - the fact there is a pumping lemma is irrelevant.

Anyway, I think the best thing to do is delete the sentence in the first paragraph (which was always tangential - it's not a significant fact to do with the pumping lemma), and delete the "Correction:" section too. I've now done that. I personally don't think any mention needs to be made of finite languages on this page. -- Bluegrass 00:12, 31 January 2007 (UTC)[reply]

Proposed Merge[edit]

I propose that this page have its information merged with Pumping lemma for regular languages, since it has the same mathematical theory and has no real distinction. There are useful details in both articles, and they discuss exactly the same thing.

Koryu Obihiro (talk) 00:40, 3 June 2014 (UTC)[reply]

Once featured[edit]

A previous version of this article was once featured. For more info, see Wikipedia talk:List of Wikipedians by featured article nominations#A few articles have been disambiguated czar 04:44, 30 August 2016 (UTC)[reply]