Talk:Pumping lemma
|
|
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.