## Introduction to the theory of átomata

Institute of Cybernetics

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.)

Tarmo Uustalu

Last update 12.5.2011