Document RAIRO-Theor. Inf. Appl. (2008)
DOI: 10.1051/ita:2007061
Hyper-minimizing minimized deterministic finite state automata
Andrew Badr1, Viliam Geffert2 and Ian Shipman31 3210 Acklen Ave., Nashville, TN 37212, USA; badr@uiuc.edu
2 Department of Computer Science, P. J. Safárik University, Jesenná 5, 04001 Kosice, Slovakia; viliam.geffert@upjs.sk
3 Department of Mathematics, University of Chicago, 5734 S. University Ave., Chicago, IL 60637, USA; ics@math.uchicago.edu
(Received July 12, 2007. Accepted November 21, 2007. Published online 20 December 2007.)
Abstract
We present the first (polynomial-time) algorithm for reducing
a given deterministic finite state automaton (DFA) into
a hyper-minimized DFA, which may have fewer states than
the classically minimized DFA. The price we pay is that the
language recognized by the new machine can differ from the
original on a finite number of inputs. These hyper-minimized
automata are optimal, in the sense that every DFA with fewer
states must disagree on infinitely many inputs. With small
modifications, the construction works also for finite state
transducers producing outputs. Within a class of finitely differing languages, the
hyper-minimized automaton is not necessarily unique. There may
exist several non-isomorphic machines using the minimum number of
states, each accepting a separate language finitely-different
from the original one. We will show that there are large
structural similarities among all these smallest automata.
Mathematics Subject Classification. 68Q70
Key words: Finite state automata -- regular languages
© EDP Sciences 2008