Pigeons and pigeon holes in finite-state machines
Samuel C. Hsieh · Journal of computing sciences in colleges · 2016
We present a basic proof strategy that is based on the pigeon-hole principle. We demonstrate the utility of this basic strategy by using the strategy to prove that a given language is not regular and to prove the minimum number of states that a finite-state machine recognizing a given language must have. The strategy can be used to prove the non-regularity of any language that is not regular. In contrast, the pumping lemma, which is commonly used for non-regularity proofs in undergraduate theory classes, cannot be used to directly prove the non-regularity of a language if the language satisfies the pumping lemma. The strategy presented here can also be used to prove a lower bound on the number of states that a finite-state machine for a given language must have. When the lower bound proved is the greatest lower bound on the number of states, the bound is the number of states in a minimum-state finite-state machine for the given language.