with
and
such that
is also in L for all i = 0, 1, 2,….
To paraphrase this, every sufficiently long string in L can be broken into
three partsin such a way that an arbitrary number of repetitions ofthe middle part
yields another string in L. We say that the middle string is “ pumped,” hence the
term pumping lemma for this result.
Proof: If L is regular, there exists a dfa that recognizes it. Let such a dfa have
states labeled q 0 , q 1 , q 2 ,…, q n . Now take a string w in L such that |w| ≥ = n +1.
Since L is assumed to be infinite, this an always be done. Consider the set of
states the automaton goes through as it processes w, say
Since this sequence has exactly |w| + 1 entries, at least one state must be
repeated, and such a repetition must start no later than the nth move. Thus, the
sequence must look like
indicating there must be substrings x, y, z of w such that
with |xy| ≤ n+1 = m and |y| ≥ 1. From this it immediately follows that
as well as
and
such that
is also in L for all i = 0, 1, 2,….
To paraphrase this, every sufficiently long string in L can be broken into
three partsin such a way that an arbitrary number of repetitions ofthe middle part
yields another string in L. We say that the middle string is “ pumped,” hence the
term pumping lemma for this result.
Proof: If L is regular, there exists a dfa that recognizes it. Let such a dfa have
states labeled q 0 , q 1 , q 2 ,…, q n . Now take a string w in L such that |w| ≥ = n +1.
Since L is assumed to be infinite, this an always be done. Consider the set of
states the automaton goes through as it processes w, say
Since this sequence has exactly |w| + 1 entries, at least one state must be
repeated, and such a repetition must start no later than the nth move. Thus, the
sequence must look like
indicating there must be substrings x, y, z of w such that
with |xy| ≤ n+1 = m and |y| ≥ 1. From this it immediately follows that
as well as