[Overview] [Previous] [Next]

Pumping Lemma Example 1

Prove that L = {anbn: n >= 0} is not regular.

  1. We don't know m, but assume there is one.

  2. Choose a string w = anbn where n > m, so that any prefix of length m consists entirely of a's.

  3. We don't know the decomposition of w into xyz, but since |xy| <= m, xy must consist entirely of a's. Moreover, y cannot be empty.

  4. Choose i = 0. This has the effect of dropping |y| a's out of the string, without affecting the number of b's. The resultant string has fewer a's than b's, hence does not belong to L. Therefore L is not regular.

Copyright 1996 by David Matuszek
Last modified Feb 18, 1996