
pumping lemma (regular languages)

(Theorem)


Let be a regular language (a.k.a. type 3 language). Then there exist an integer such that, if the length of a word is greater than , then where are subwords such that
 The length of the subword is less than .
 The subword cannot be empty (although one of or might happen to be empty).
 For all integers , it is the case that belongs to , where exponentiation denotes repetition of a subword times.
An important use of this lemma is to show that a language is not regular. (Remember, just because a language happens to be described in terms of an irregular grammar does not automatically preclude the possibility of describing the same language also by a regular grammar.) The idea is to assume that the language is regular, then arrive at a contradiction via this lemma.
An example of such a use of this lemma is afforded by the language
Let be the number whose existence is guaranteed by the lemma. Now, consider the word
. There must exist subwords such that and must be of length less than . The only possibilities are the following





In these cases, would have the following form:





It is easy to see that, in each of these five cases,
. Hence cannot be a regular language.

"pumping lemma (regular languages)" is owned by rspuzio.


(view preamble)
See Also: pumping lemma (contextfree languages)
Other names: 
pumping lemma 
Crossreferences: easy to see, contradiction, terms, regular, word, length, integer, language, type, regular language
This is version 5 of pumping lemma (regular languages), born on 20061028, modified 20061225.
Object id is 8489, canonical name is PumpingLemmaRegularLanguages.
Accessed 426 times total.
Classification:
AMS MSC:  68Q42 (Computer science :: Theory of computing :: Grammars and rewriting systems) 



Pending Errata and Addenda







