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_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.
Brzozowski and Tamm @cite_4 showed that every regular language defines a unique NFA, which they call . The átomaton is built upon the minimal DFA ( ^ DM ) for the language, defining its states as non-empty intersections of complemented or uncomplemented right languages of ( ^ DM ), i.e., the atoms of the language. They also observed that the atoms correspond to intersections of complemented or uncomplemented left quotients of the language. Then they proved that the átomaton is isomorphic to the reverse automaton of the minimal deterministic DFA for the reverse language.