Thursday, 21 April 2011, 14:00
Cybernetica Bldg (Akadeemia tee 21), room B101
Slides from the talk [pdf]
Abstract: We show that every regular language defines a unique nondeterministic 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 introduce "atomic" NFAs, in which the right language of every state is a union of some atoms. This class of automata is a generalization of residual automata in which the right language of any state is a left quotient (which we prove to be a union of atoms), and includes also átomata (where the right language of any state is an atom), trim DFAs, and the trim parts of universal automata.
Our main result is a characterization of the class of NFAs for which the subset construction yields a minimal DFA. More specifically, we show that the subset construction applied to a trim NFA produces a minimal DFA if and only if the reverse automaton of that NFA is atomic. This is a generalization of Brzozowski's method for DFA minimization by double reversal.
(Joint work with Janusz Brzozowski, accepted to DLT 2011.)