In this work we use a framework of finite-state automata constructions based on equivalences over words to provide new insights on the relation between well-known methods for computing the minimal deterministic automaton of a language.
@cite_13: An algorithm is given for minimizing the number of states in a finite automaton or for determining if two finite automata are equivalent. The asymptotic running time of the algorithm is bounded by k n log n where k is some constant and n is the number of states. The constant k depends linearly on the size of the input alphabet.
@cite_4: We show that every regular language defines a unique nondeterministic finite automaton (NFA), which we call "atomaton", whose states are the "atoms" of the language, that is, non-empty intersections of complemented or uncomplemented left quotients of the language. We describe methods of constructing the atomaton, and prove that it is isomorphic to the normal automaton of Sengoku, and to an automaton of Matz and Potthoff. We study "atomic" NFA's in which the right language of every state is a union of atoms. We generalize Brzozowski's double-reversal method for minimizing a deterministic finite automaton (DFA), showing that the result of applying the subset construction to an NFA is a minimal DFA if and only if the reverse of the NFA is atomic.
In conclusion, we establish a connection between well-known independent minimization methods through Theorem . Given a DFA, the left languages of its states form a partition on words, (P ), and thus, each left language is identified by a state. Intuitively, Moore's algorithm merges states to enforce the condition of Theorem , which results in merging blocks of (P ) that belong to the same Nerode's equivalence class. Note that Hopcroft's partition refinement method @cite_13 achieves the same goal at the end of its execution though, stepwise, the partition computed may differ from Moore's. On the other hand, any co-deterministic NFA satisfies the right-hand side of Equation hence, by Lemma , satisfies the condition of Theorem . Therefore, the double-reversal method, which essentially determinizes a co-determinized NFA, yields the minimal DFA. Finally, the left-right duality (Lemma ) of the language-based equivalences shows that the condition of Theorem is equivalent to that of Brzozowski and Tamm @cite_4 .