pumping lemma (regular languages)
Lemma 1.
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
-
1.
The length of the subword is less than .
-
2.
The subword cannot be empty (although one of or might happen to be empty).
-
3.
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
-
1.
-
2.
-
3.
-
4.
-
5.
In these cases, would have the following form:
-
1.
-
2.
-
3.
-
4.
-
5.
It is easy to see that, in each of these five cases, . Hence cannot be a regular language.
Title | pumping lemma |
---|---|
Canonical name | PumpingLemmaregularLanguages |
Date of creation | 2013-03-22 16:21:17 |
Last modified on | 2013-03-22 16:21:17 |
Owner | rspuzio (6075) |
Last modified by | rspuzio (6075) |
Numerical id | 9 |
Author | rspuzio (6075) |
Entry type | Theorem |
Classification | msc 68Q42 |
Synonym | pumping lemma |
Related topic | PumpingLemma |