Math for the people, by the people.
Encyclopedia | Requests | Forums | Docs | Wiki | Random | RSS
 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)

 View style: HTML with imagespage imagesTeX source

 Other names: pumping lemma

Cross-references: easy to see, contradiction, terms, regular, word, length, integer, language, type, regular language

This is version 5 of pumping lemma (regular languages), born on 2006-10-28, modified 2006-12-25.
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)