- a hole or small recess for pigeons to nest
- a small open compartment (as in a desk or cabinet) for keeping letters or documents
- a neat category which usu. fails to reflect actual complexities.

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 = {ab:
*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 a^{i} and a^{j} end in the
same state.
From this state,

- b
^{i}must end in a final state, because a^{i}b^{i}is in L; and - b
^{i}must end in a nonfinal state, because a^{j}b^{i}is not in L.

Copyright © 1996 by David Matuszek

Last modified Feb 18, 1996