2011 | OriginalPaper | Buchkapitel
Some Remarks on Automata Minimality
verfasst von : Antonio Restivo, Roberto Vaglica
Erschienen in: Developments in Language Theory
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
It is well known that the minimization problem of deterministic finite automata (
DFAs
) is related to the indistinguishability notion of states (cf. [HMU00]). Indeed, a well known technique to minimize a DFA, essentially, consists in finding pairs of states that are equivalent (or
indistinguishable
), namely pairs of states (
p
,
q
) such that it is impossible to assert the difference between
p
and
q
only by starting in each of the two states and asking whether or not a given input string leads to a final state. Since, in the testing states equivalence, the notion of initial state is irrelevant, some of the main techniques for the minimization of automata, such as Moore’s algorithm [Moo56] and Hopcroft’s algorithm [Hop71], do not care what is the initial state of the automaton, when applied to accessible automata (i.e. such that all states can be reached from the initial state). Therefore a natural question that arises is, for accessible automata, on what does minimality depend? Obviously, it depends on both the automata transitions and the set of final states. In this paper, our main focus is to investigate to what extent minimality depends on the particular subset of final states.