Pumping Lengths
Pumping Lemma describes a fundamental property of regular languages, in simple terms it states that in order for a language to be regular, sufficiently long words may be pumped, where pumped means that a given section of the middle of the word, can be repeated a number of times to produce a new word which still lies within the same language.
Formally, Let
be a regular language. Then there exists an integer
depending only on
such that every string
in
of length at least
(the "pumping length") can be written as
(i.e.,
can be divided into three substrings), satisfying the following conditions:
Why Is This Relevant?
This method can be used to show a language is not regular, since if it meets the above criteria then it must be a regular language, so a proof by contradiction can be used to show which languages are not regular and thus not able to be modelled by NFAs or DFAs.


