82 F1NKCE AUTOMATA
V y = uvwFigure 2.55: The path (q~,~,q~,.,q,=~.,q,~,q~,~,f)~
Example 2.60 (0” In 1 n > 0) - is not a regular language.
Proof. By way of contradiction, assume that L = {Onln 1 n > 0) is regular.
Then, L is accepted by a DFA 1M. Let s be the number Of states in M.
Consider a string a! = 0” 1’ E L. Choose x = E, y = O”, and x = 1”. Note that
IYI = IO”1 = s. By the pumping lemma, Q! can be written as a = xuvwx 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 chat xuwz = O”-l”l1” E L. However, since v # &, we
have s - Iv1 < s, contradicting the definition of L. cl
From the above example, we can summarize in the following how to prove,
by the pumping lemma, that a given language L is not regular:
(1) Assume that L is accepted by a DFA M of s states.
(2) Select a string clr E L, with Ial > s. -
(3) Divide CY into three parts o = xyx with 1~1 > s. -
(4) For any way of dividing y into three parts y = uvw with v # &, argue
that XUV~WZ 4 L for some k > 0. -
Since s is the size of the DFA M accepting L, and since the DFA M is
unknown to us, we do not know how large s is. Therefore, steps (a>, (3)
and (4) must work for all positive integers s. Similarly, the breakdown of y
into y = uvw depends on the unknown DFA M, and so is unknown to us.
Therefore, we must argue, in step (4) g a ainst all possible way of dividing y
into uvw, as long as v # &.
On the other hand, we are free to select the strings x, y, Z, as long as
Cl!= xyz E L and lyl > - s. Indeed, the choice of x = &, y = 0” and z = 0”
in the above example made the proof simple. (The reader may verify this
claim by trying the choice of o = 02” 12’, x = O”, y = 0” 1” and z = 1’ to see
how complicated the corresponding proof is.) In general, the main difficulty
of using the pumping lemma to prove a language nonregular is to determine
which’ strings x, y, x are to be used in the proof. The next two examples
illustrate this point.
Example 2.61 Show thut L = {@pR I p E (0, l}+} is not a regular language.
Proof. By way of contradiction, assume that L is a regular language, accepted
by a DFA M of s > 0 states. Following the idea of Example 2.60, we select a