2.8 Pumping Lemmas 83
string a = 0”110” E L, and let II: = E, y = OS, and x = 110”. By the pumping
lemma, y can be written as y = uvw such that v # E and xuv*wx C L.
This means that for any k > 0, XUV~WX E L. When k = 0, this means-that
xuwx = Os-l”lllOs E L. However, we observe that OS-l”lllOs is not of the
form ,OPR: Since Iv1 > - 1, either the string 0”-1~~110” is of an odd length (when
Iv1 is odd) or its first half contains two l’s and the second half has no 1. This
is a contradiction. 0
Example 2.62 Show thut L = (PPRr I P E {0,1)+/Y E {O,l)‘) is ?--lot
regular.
Proof. By way of contradiction, assume that L is a regular language, accepted
by a DFA A4 of s states. We need to choose a string Q! E L with Ial > s and
divide it into three substrings Q = xyz with IyI > s. Note that if we dO it like
in the last example, with o = OS llO”, x = E, y- 0’ and z = llO”, then the
proof does not work:
(1) The string Os-~“rllo” is of the form ,&?“r, with ,0 = 0”-1”[1 and y = OIVl;
(2) The string Os+“lV~llOs, with k > 2, is of the form /3pRr, with p = 0.
To fix this problem, we choose Q = -010s110s10 E L (p = OlO”1 and y = E),
and let x = 01, y = OS, and x = 110’10. Note that the only prefix of ~0%
that is of the form @pR is the whole string, and it holds only for t = s.
More precisely, we check that, by the pumping lemma, y can be written as
Y = uvw such that v # E and xuv*wx C L. This means that for any K > 0,
XZ&WZ E L. In particular, xuv2wx = OiOs+~w~llOs10 E L. Now, xuv2wz~ L
means 010”+1”1110”10 = PPRr for some ,0, y E (0, 1)‘. Since there are only
two occurrences of the substring 010 in this string (as the prefix and suffix),
,0 must contain the prefix 010 and PR must contain the suffix 010 and y must
be the empty string. In other words, OIOs+l”lllOs10 = @YR. However, this
is obvious impossible, as explained in the proof of the last example. We have
reached a contradiction.^0
It is interesting to note that (PrPRIP E (0, l}+,y E (0, 1)‘) is equal to
the language with the following regular expression:o(0 u l)+o u l(0 u 1)fl.Thus, it is a regular language.Example 2.63 Show that the language L = {0”10”10J’10~ 1 n, m, p > - 1, 4 f
nm (mod p)} is not regular.Solution. By way of contradiction, assume that L is a regular language, ac-
cepted by a DFA M of s states. Consider the string Q! = OIOs+llOs’llOs+l.
Apply the pumping lemma to string a, with x = OIOs+llOs+l 10, y = 0” and
x = E. Then, the suffix y = 0” can be written as uvw such that v # E and for