A condition characterizing the class of regular languages which have several nonisomorphic minimal reversible automata is presented. The condition concerns the structure of the minimum automaton accepting the language under consideration. It is also observed that there exist reduced reversible automata which are not minimal, in the sense that all the automata obtained by merging some of their equivalent states are irreversible. Furthermore, a sufficient condition for the existence of infinitely many reduced reversible automata accepting a same language is given. It is also proved that, when the language is accepted by a unique minimal reversible automaton (that does not necessarily coincide with the minimum deterministic automaton), then no other reduced reversible automata accepting it can exist.
Minimal and Reduced Reversible Automata / G.J. Lavado, G. Pighizzini, L. Prigioniero. - In: JOURNAL OF AUTOMATA, LANGUAGES AND COMBINATORICS. - ISSN 1430-189X. - 22:1-3(2017), pp. 145-168.
Minimal and Reduced Reversible Automata
G.J. Lavado
;G. Pighizzini
;L. Prigioniero
2017
Abstract
A condition characterizing the class of regular languages which have several nonisomorphic minimal reversible automata is presented. The condition concerns the structure of the minimum automaton accepting the language under consideration. It is also observed that there exist reduced reversible automata which are not minimal, in the sense that all the automata obtained by merging some of their equivalent states are irreversible. Furthermore, a sufficient condition for the existence of infinitely many reduced reversible automata accepting a same language is given. It is also proved that, when the language is accepted by a unique minimal reversible automaton (that does not necessarily coincide with the minimum deterministic automaton), then no other reduced reversible automata accepting it can exist.Pubblicazioni consigliate
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.