[Overview] [Previous] [Next]

The Pigeonhole Principle

pigeonhole: (pij' un hole) n
  1. a hole or small recess for pigeons to nest
  2. a small open compartment (as in a desk or cabinet) for keeping letters or documents
  3. a neat category which usu. fails to reflect actual complexities.
pigeonhole principle: if n objects are put into m containers, where n > m, then at least one container must hold more than one object.

The pigeonhole can be used to prove that certain infinite languages are not regular. (Remember, any finite language is regular.)

As we have informally observed, dfas "can't count." This can be shown formally by using the pigeonhole principle. As an example, we show that L = {an timesbn times: n > 0} is not regular. The proof is by contradiction.

Suppose L is regular. There are an infinite number of values of n but M(L) has only a finite number of states. By the pigeonhole principle, there must be distinct values of i and j such that ai and aj end in the same state. From this state,

Since the state reached cannot be both final and nonfinal, we have a contradiction. Thus our assumption, that L is regular, must be incorrect. Q.E.D.


Copyright 1996 by David Matuszek
Last modified Feb 18, 1996