Theory of átomata

Abstract. We show that every regular language defines a unique non-deterministic finite automaton (NFA), which we call “átomaton”, 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 átomaton, and prove that it is iso-morphic to the normal automaton of Sengoku, and to an automaton of Matz and Potthoff. We study “atomic ” NFA’s in which the right lan-guage 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.