- If an infinite language is regular, it can be defined by a dfa.
- The dfa has some finite number of states (say,
*n*). - Since the language is infinite, some strings of the language
must have length >
*n*. - For a string of length >
*n*accepted by the dfa, the walk through the dfa must contain a cycle. - Repeating the cycle an arbitrary number of times must yield another string accepted by the dfa.

The proof is always by contradiction. A brief outline of the technique is as follows:

- Assume the language L is regular.
- By the pigeonhole principle, any sufficiently long string in L must repeat some state in the dfa; thus, the walk contains a cycle.
- Show that repeating the cycle some number of times ("pumping" the cycle) yields a string that is not in L.
- Conclude that L is not regular.

- We don't know the dfa (if we did, the language would be regular!). Thus, we have do the proof for an arbitrary dfa that accepts L.
- Since we don't know the dfa, we certainly don't know the cycle.

- We get to choose the string (but it must be in L).
- We get to choose the the number of times to "pump."

Copyright © 1996 by David Matuszek

Last modified Feb 18, 1996