Thursday, December 4, 2008

An interesting example on the Pumping Lemma



I had some problems understanding the Pumping Lemma and while reading a book (Introduction to Automata Theory Languages and Computation 2nd edition page 128) I came across an interesting example of how they described the Pumping Lemma as a game:

The Pumping Lemma as an Adversarial Game

... The pumping lemma is an important example in a theorem that involves several alternations of 'for-all' and 'there-exists' quantifiers that can be thought of as a game between two players, since it in effect 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 w such 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 doesn't reveal to player 1 what n is; player 1 must devise a play for all possible n's.

3. Player 1 picks w, which 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; y != epsilon and /xy/ <= n. Again player 2 does not have to tell player 1 what x,y, and z are, although they must obey the constraints.

5. Player 1 "wins" by picking k, which may be a function of n,x,y, and z, such that x(y^k)z is not in L.

1 comment:

Unknown said...

Can't say nothing else than thanks! I've spent hours trying to get the hang of this, and this approach really helped. Thanks a lot.