2.8 Pumping Lemmas 81
also have uv*w C L. (E.g., uv2w is in L because S(qo,uv2w) = J(qi,vvw) =
@Ii f VW) = qqiG) = !-If 0) cl
Now, for a given langauge L, if we can prove that the necessary condition
of the pumping lemmadoes not hold with respect to any s > 0, then L is not
regular.
Example 2.58 {Of-' 1 p is a prime} is not a regular language.
Proof. By way of contradiction, assume that L = (0” 1 p is a prime number}
is regular. Then, L is accepted by a DFA AI. Let s be the number of states
in AI. Consider a prime number p > s. Note that OJ’ E L and lOPI = p > s.
Therefore, by the pumping lemma, OP can be written as OJ-’ = uvw such that
v # & and uvw E L.
Let i = IuI + lull and j = Ivl. Th en, the condition uvw C L means that,
for any k > 0, uvkw = Oi+kj E L. Or, equivalently, for any% > 0, i + kj is
a prime. In particular, when Jc = 0, it means that i is a prime. So, i > 2.
When k = i, this means that i(1 + j) is a prime. However, since v # E,we
have j = Iv1 > - 1, and so i(1 +j) is not a prime. This is a contradiction. a
Note that in the above example, the underlying language is over a singleton
alphabet (0). For languages over an alphabet with more than one symbol, the
above pumping lemma is not convenient and sometimes even not sufficient.
For instance, consider the language {Onln I n > 0). When we follow the
argument in the proof of the above example, weget O”1” = uvw for some
strings u, v, w. There are three possible cases for v: (1) v contains only symbol
0; (2) v contains only symbol 1; and (3) v contains both symbols 0 and 1. A
complete proof needs to produce a contradiction for each case. This makes the
proof more complicated and tedious. The following stronger pumping lemma
is a nice tool to avoid this problem.
Lemma 2.59 (Pumping Lemma, Stronger Form). If a language L is accepted
by a DFA M with s states, then for any string CI E L with Ial > - s and any
way of breaking clr into a = xyz with ] yl - > s, y can be written as y = uvw
such that v # E and xuv*wx C - L.
Probf. Consider the transition diagram of AI. Since a = xyx E L, the
computation path 7r of a goes from the initial state qo to a final state qf. The
path x can be divided into three subpaths, associated with the strings x, y
and x, respectively. Assume that the second subpath 7r2, which is associated
with y, is from state q1 to state q2. Then, 7r2 has exactly 1~1 edges and, by
the same argument as in the proof of Lemma 2.57, 7r2 can be further divided
into three subpaths, with the middle one being a cycle (see Figure 2.55). Let
u, v, and w be the strings associated with the three subpaths, respectively.
Then, y = uvw and v $5 E. Since v is associated with a cycle, we also have
xuv*wx c - L.^0