80 FINITE AUTOMATA
Figure 2.53: An NFA for Exercise 5.
2.8 Pumping Lemmas
Not all languages are regular. In fact, there are uncountably many languages
over an alphabet C (cf. Example 5.18) but only countably many of them are
regular (there are at most cn possible regular expressions of length n for some
constant c > 0). Therefore, most languages are not regular.
In the last section, we have used the simple characterization of Corollary
2.49 for regular languages to prove that some languages are not regular. How-
ever, this method involves the analysis of equivalence classes of the relation
RL, and is sometimes difficult to apply. In this section, we introduce another
necessary condition for regularity of languages which can be used to prove
that a language is nonregular. In the following, we write, for any string V, V*
to denote the set (2))‘.
Lemma 2.57 (Pumping Lemma). If a language L is accepted by a DFA A4
with s states, then every string x in L with 1x1 > - s can be written as x = uvw
such that v # E and uv*w C L.Proof. Consider the transition diagram of M. Since x E L, the computation
path x of x starts from the initial state 40 and ends at a final state qf. The
concatenation of the labels over the path 7r is exactly the string x. The path
7r has exactly 1x1 edges because each edge is labeled by a symbol. Thus, the
path x contains a vertex sequence of 1x1 + 1 elements. Since 1x1 > - s, some
state qi occurs more than once in the sequence. Break the path x into three
subpaths at the first and second occurrences of qi. That is, the first subpath
is from state qo to the first occurrence of qi, the second subpath is a cycle
from the first q; to the second qi, and the third subpath is from the second qi
to qf (see Figure 2.54).
Let u, v, and w be the concatenations of the labels of the three subpaths,
respectively. Then, x = UVW, and v # &. Since v is associated with a cycle, we
Figure 2.54: The path (qo,*,q~,=*,qi,,qf)o