Talk:Pumping lemma
From Wikipedia, the free encyclopedia
 |
|||||
| 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. | |||||
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.
Contents |
[edit] The Hebrew Interwiki in this article
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)
[edit] CFG version notation confusion
There are two i's, one for a^ib^ic^i, and the other for v^ixy^i. This creates unnecessary confusion.
[edit] Disambiguation?
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?
[edit] Context?
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)
- I added another link to computability theory. The link to formal languages also gives context. CMummert 03:04, 17 December 2006 (UTC)
[edit] Finite languages
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)
