[Overview] [Previous] [Next]

Pumping Lemma Example 2

Prove that L = {anbk: n > k and n >= 0} is not regular.

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

  2. Choose a string w = anbk where n > m, so that any prefix of length m consists entirely of a's, and k = n-1, so that there is just one more a than b.

  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 before, so it has either fewer a's than b's, or the same number of each. Either way, the string does not belong to L, so L is not regular.
Q.E.D.


Copyright 1996 by David Matuszek
Last modified Feb 18, 1996