We show that every regular language defines a unique nondeterministic finite
automaton (NFA), which
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.
Date and Venue
Start Date
Venue
: FC 029 (A2), DCC-FCUP
Speaker
Janusz Brzozowski (University of Waterloo, ON, Canada)
Area
Semigroups, Automata and Languages