[Overview] [Previous] [Next]

Applying the Pumping Lemma

Here's a more formal definition of the pumping lemma:

If L is an infinite regular language, then there exists some positive integer m such that any string w is a member of L whose length is m or greater can be decomposed into three parts, xyz, where

Here's what it all means: To use this lemma, we need to show:
  1. For any choice of m,
  2. for some w is a member of L that we get to choose (and we will choose one of length at least m),
  3. for any way of decomposing w into xyz, so long as |xy| isn't greater than m and y isn't empty string,
  4. we can choose an i such that xyiz is not in L.
We can view this as a game wherein our opponent makes moves 1 and 3 (choosing m and choosing xyz) and we make moves 2 and 4 (choosing w and choosing i). Our goal is to show that we can always beat our opponent. If we can show this, we have proved that L is not regular.


Copyright 1996 by David Matuszek
Last modified Feb 18, 1996