• For a string of length > n accepted by the DFA, the walk through the
DFA must con tain a cycle.
• Repeating the cycle an arbi trary num ber of times should yield another
string accepted by the DFA.
The “pumping lemma” for regular languages is another way of showing
that a given infinnite language is not regular. The proof is always done by
“contradiction”. The technique that is followed is as outlined below:
(i) Assume that the language L is regular.
(ii) By Pigeon-hole principle, any sufficiently long string in L should
repeat some state in the DFA, and therefore, the walk contains a
“cycle”.
(iii) Show that repeating the cycle some number of times (“pumping”
the cycle) yields a string that is not in L.
(iv) Conclude that L is not regular.
1.8.2 Applying the Pumping Lemma
Def i ni tion of Pumping Lemma
If L is an infinite regular language, then there exists some positive integer ‘m’
such that any string w L
∈ , whose length is ‘m’ or greater can be decomposed
into three parts, xyz where
(i) | xy | is less than or equal to m.
(ii) | y | > 0,
(iii) w xy z
i
i
=
is also in L for all i = 0, 1, 2, 3, ……
To use this lemma, we need to show:
(i) For any choice of m,
(ii) For some w L
∈ that we get to choose (and we will choose one of
length at least ‘m’).
(iii) For any way of decomposing w into xyz, so long as |xy| is not
greater than m and y is not λ,
(iv) We can choose an i such that xy
i z is not in L.
Ì Exam ple 1.8.1: Prove that L a b n
n n
=
≥
{
:
}
0 is not regular.
Solu tion
(i) We don’t know m, but let us assume that there is one.
(ii) Choose a string w = a
n b
n , where n > m, so that any prefix of length
‘m’ consists only of a’s.
94
Theory of Automata, Formal Languages and Computation