Schaum's Outline of Discrete Mathematics, Third Edition (Schaum's Outlines)

CHAP. 12] LANGUAGES, AUTOMATA, GRAMMARS 309

Fig. 12-3

Sinceb^2 is accepted, but notlorb, we need three states,s 0 , the initial state, ands 1 ands 2 with an arrow
labeledbgoing froms 0 tos 1 and one froms 1 tos 2. Also,s 2 is an accepting state, but nots 0 nors 1. This gives
the graph in Fig. 12-3(a). On the other hand, if there is ana, then we want to go back tos 0 , and if we are ins 2
and there is ab, then we want to stay ins 2. These additional conditions give the required automatonMwhich is
shown in Fig. 12-3(b).

Pumping Lemma

LetMbe an automaton overAwithkstates. Supposew=a 1 a 2 ···anis a word overAaccepted byMand
suppose|w|=n>k, the number of states. Let

P=(s 0 ,s 1 ,...,sn)

be the corresponding sequence of states determined by the wordw. Sincen>k, two of the states inPmust be
equal, saysi=sjwherei<j. Letwbe divided into subwordsx,y,zas follows:

x=a 1 a 2 ···ai,y=ai+ 1 ···aj,z=aj+ 1 ···an

As shown in Fig. 12-4,xyends insi=sj; hencexymalso ends insi. Thus, for everym,wm=xymzends
insn, which is an accepting state.

Fig. 12-4

The above discussion proves the following important result.

Theorem 12.3 (Pumping Lemma): SupposeMis an automaton overAsuch that:
(i)Mhaskstates. (ii)Maccepts a wordwfromAwhere|w|>k.
Thenw=xyzwhere, for every positivem, wm=xymzis accepted byM.
The next example gives an application of the Pumping Lemma.

EXAMPLE 12.8 Show that the languageL={ambm|mis positive}is not regular.
SupposeLis regular. Then, by Theorem 12.2, there exists a finite state automatonMwhich acceptsL.
SupposeMhaskstates. Letw=akbk. Then|w|>k. By the Pumping Lemma (Theorem 12.3),w=xyz
whereyis not empty andw 2 =xy^2 zis also accepted byM.Ifyconsists of onlya’s or onlyb’s, thenw^2 will not
have the same number ofa’s asb’s. Ifycontains botha’s andb’s, thenw 2 will havea’s followingb’s. In either
casew 2 does not belong toL, which is a contradiction. ThusLis not regular.