Better Know a Theorem: Minimal Automata

31Mar08

One of my favourite courses as an undergraduate was “Introduction to the Theory of Computation.” It was taught by Michael Sipser, who also wrote the textbook, and one thing I liked about it was that the presentation was very natural and easy to read. I recently came across a really nice old result which could have been included (but wasn’t).

A deterministic finite-state automaton (DFA) is basically the simplest “computer” imaginable. It is comprised of

• an input alphabet
• a finite number of “states” which I will depict as circles
• one state must be designated the initial state
• every state is either an accepting or a rejecting state
• for each state, and each character of the input alphabet, an arrow to another state

What does a DFA compute? It computes a language in the sense that, for a given a string of characters from the input alphabet, the DFA can either accept or reject that string, and the DFA’s language is the set of all accepted strings. To determine if a particular string belongs to the language,

1. start at the initial state
2. for each character of the string, follow the arrow labeled with that character
3. accept if you end in an accepting state, reject if you end in a rejecting state

E.g. in the diagram below I have tried to illustrate a simple DFA with 2 states. The alphabet is {x, y} and the DFA accepts a string if and only if it contains an odd number of x’s.

It is possible for two different DFAs to recognize the same language; if this is the case we call them equivalent. Thus, if I hand you a DFA, it is natural to ask “is there any other equivalent DFA with a fewer number of states? what is it?” We call a DFA minimal if no other equivalent DFA has fewer states. Today’s better know a theorem is the following:

A DFA is minimal if and only if every state is accessible and every pair of states is distinguishable, where

• a state is accessible if there is some path to it from the initial state
• two states s, t are distinguishable if there is a string w so that the DFA, when started in s, accepts w, but would not accept w if started in t (or vice-versa)

It is not too hard to see why every minimal DFA is accessible and distinguishable: if a state is inaccessible we can just delete it, and if two states are equivalent we can coalesce them, contradicting minimality. One way to prove the other direction is via the Myhill-Nerode theorem which provides an elegant characterization of languages accepted by DFAs.

One of the things covered in Sipser’s text is the pumping lemma, which is one way to prove that a given language is not recognized by any FSA. Myhill-Nerode provides another solution which I think would have been neat to learn in the undergrad computation class.

Algorithmically, the theorem gives an efficient method to minimize a given DFA: repeatedly delete inaccessible states and coalesce equivalent pairs of states. On the other hand, looking at some slightly more complicated computing devices, minimizing push-down automata is undecidable, while minimizing nondeterministic finite-state automata is “hard”.