4.1. PROVING LANGUAGES NOT TO BE REGULAR 127

PROOF: Suppose L is regnlar. Then L= L{.A) for some DF.A .4. Suppose .4 has n states. Now, consider any string w of length n or more, say w = а\п->-- ((, ,

where rn > n and each (ij is an input symbol. For i - 0,1----, n define state

Pi to be 6(qQ, 1(12 * where 5 is the transition function of .4, ami qo is the start statP of .4. That i.s-, p/ is the state A is in after reading the first i symbols ol w. Note that po = Qo.

By tin- pigeonhol(> principle, it is not possible for the ?! + 1 different p,\s for г = 0,1. ?i to be distinct, since* there are only n different states. Thus, we can find two (lifTerem integers i and j, with 0 < i < i < n, such that /); = pj. Now, w( can break w = xyz as follows:

1. = rti(72 -ft,.

2. у = ,-,ifl,v2 -Hj-

3. г = jifij a -a !.

That is, X takes us to p, once; у takes us from Pi back to Pi (since is also and г is the balance of w. The relationships amemg the; strings and states are sugg<>ste<l by Fig. 4.1. Note that x may he cmpt}, in the <-ase that i = 0. .Al.so, z may be empty i£ j - n = m. However, у can not be tnipty, since i is strictly less than j.

JC = z =

Start Oj ... a. Hjj

Figure 4.1: Every string longer than the number of stales must cause a state to repeal

Now, consider what happens if the automaton .4 receives the input xyz for any k>(]. If = 0, then the automaton goes from th(> start state (which is also po) to Pi on input x. Since p, is also pj, it must be that A goes from p, to the accepting state shown in Fig, 4,1 on input z. Thus, .1 accepts .тг.

If A: > 0, then .4 goes from 170 to p,- on in]nit x. circles fnun p, to pi к times on input i/*, and then goiis to the accepting state on input z. Thus, for any > 0, xyz is also acc(>pted by A: that is, xyz is in L. □

4.1.2 Applications of the Pumping Lemma

Let us sio some examples of how the ])umping lemma is used. In each case, we shall propose a language and use tin; pumping lenuua to prove that the language is not regular.

The Pumping Lemma as an Adversarial Game

Recall our discussion from Section 1.2.3 where we pointed out that a theorem whose statement involves several alternations of for-all and there-exists quantifiers can be thought of as a game between two players. The pumping lemma is an important example of this type of theorem, since it in elfect involves four different quantifiers: for all regular languages L there exists n such that for all w in L with \w\ > n there exists xyz equal to vi snch that , We can see the application of the pumping lemma as a game, in which:

1. Player 1 picks the language L to be proved nonregular.

2. Player 2 picks n, but doesnt reveal to player 1 what n is; player 1 must devise a play for all possible 7is.

3. Player 1 picks w, whicli may depend on n and which must be of length at least n.

4. Player 2 divides w into x, y, and z, obeying the constraints that are stipulated in the pumping lemma; у Ф e and \xy\ < n. Again, player 2 docs not have to tell player 1 what x, y, and z are, although they nmst obey the constraints.

5. Player 1 wins by picking fc, which may be a function of n. x, y. and z, such that хуг is not in L.

Example 4.2 : Let us show that the language Lq consisting of all strings with an equal number of Os and Is {not in any particular order) is not a regular language. In terms of the two-player game described in the box on The Pumping Lemma as an Adversarial Game, we shall be player 1 and we must deal with whatever choices player 2 makes. Suppose n is the constant that must exist if Lcq is regular, according to the pumping lemma; i.e., player 2 picks ji. We shall pick w = 0 1 , that is, n Os followed by n Is, a string that surely is in Leg.

Now, player 2 breaks our ги up into xyz. All we know is that у e, and \xy\ < n. However, that information is very useful, and wc win as fofiows. Since < ri, and xy comes at the front of w, we know that x and у consist only of Os. The pumping lemma tells us that хг is in Lg, if Leg is regular. This conclusion is the case fc = 0 in the pumping lemma.- However, хг has n Is, since all the Is of tt; are in z. But xz also has fewer than л Os, because we

Observe in what follows that we could have also siicccRdfid by picking - 2, or indeed any value of к other than 1.

4.L PROVING LANGUAGES NOT TO BE REGULAR 129

lost the Os of y. Since у ф e. v/e know that there can be no more than n - 1 Os among X and z. Thus, after assuming Lcq is a regular language, we have proved a fact known to be false, that xz is in Lfiq. We have a proof by contradiction of the fact that Lq is not regular. □

Example 4.3: Let s show that the langnage L consisting of all strings of Is whose length is a prime is not a regular language. Suppose it were. Then there would be a constant n satisfying the conditions of the pumping lemma. Consider some prime p > n + 2\ there must be such a p, since there are an infinity of primes. Let w = I.

By the pumping lemma, we can break tv - xyz such that у ф t and \xy\ < n. Let \y\ =m. Then \xz\=p~m. Now consider the string xy~z, which must be in Lpr by the pumping lemma, if Lpr really is regular. However,

\xy~z\ = \xz\ + (p - m)\y\ =p-m + {p~ m)m = {m + l)(p - m)

It looks like \xyP~ -z\ is not a prime, since it has two factors m + 1 and p - m. However, we must check that neither of these factors are 1, since then {m + \){p- m) might be a prime after all. But m + 1 > 1, since у ф e tells us m > 1. Also, p -тп> I, since p> n + 2 was chosen, and m <n since

m=\y\< \xy\ < n

Thus, p - m > 2.

Again we have started l>y assuming the language in question was regidar, and we derived a contradiction by showing that some string not in the language was required by the pumping lemma to bo in the language. Thus, we conclude that L,jr is not a regular language. □

4.1.3 Exercises for Section 4.1

Exercise 4.1.1: Prove that the following are not regular languages.

a) {0 ! I > 1}. This language, consisting of a string of Os followed by an equal-length string of Is, is the language Lni we considered informally at the beginning of the section. Here, you should apply the pumping lemma in the proof.

b) The set of strings of balanced parentheses. These are the strings of characters ( and that can appear in a well-fonned arithmetic expression.

* c) {0 10 I n> 1}.

d) {0 1 2 1 71 and тп are arbitrary integers}.

e) (O ! I n < m).

f) (ОЧ I 71 > 1}.