A positive integer 
is a pumping length for a formal language 
if every string 
with 
can be written 
with 
, 
, and 
for every nonnegative
integer 
. The pumping lemma for regular
languages states that every regular language has at least one pumping length
(Hopcroft et al. 2000).
For a language recognized by a finite automaton, take 
to be the number of states. Any accepting computation on a string
of length at least 
must revisit a state among its first 
steps. The portion of the string read around this loop is
, and traversing the loop any number of times gives
the pumped strings.
The lemma is commonly used in a proof by contradiction to prove that a formal language is not a regular language. Its condition is necessary but not sufficient: satisfying the pumping property alone does not prove that a language is a regular language.
