Document RAIRO-Theor. Inf. Appl. (2008)
DOI: 10.1051/ita:2008022
Minimal NFA and biRFSA Languages
Michel Latteux1, Yves Roos1 and Alain Terlutte21 Laboratoire d'Informatique Fondamentale de Lille, UMR CNRS 8022, Université de Lille 1, 59655 Villeneuve d'Ascq Cedex, France; michel.latteuxyves.roos@lifl.fr
2 Équipe Grappa-EA 3588, Université de Lille 3, Domaine universitaire du "Pont de bois", BP 149, 59653 Villeneuve d'Ascq Cedex, France; alain.terlutte@univ-lille3.fr
(Received June 1st, 2006. Accepted February 25, 2008. Published online 23 May 2008.)
Abstract
In this paper, we define the notion of biRFSA which is a residual finate state
automaton (RFSA) whose the reverse is also an RFSA. The languages recognized by
such automata are called biRFSA languages. We prove that the canonical RFSA of a
biRFSA language is a minimal NFA for this language and that each minimal
NFA for this language is a sub-automaton of the canonical RFSA. This leads
to a characterization of the family of biRFSA languages.
In the second part of this paper, we define the family of biseparable automata.
We prove that every biseparable NFA is uniquely minimal among all NFAs recognizing
a same language, improving
the result of H. Tamm and E. Ukkonen for bideterministic automata.
Mathematics Subject Classification. 68Q45.
Key words: Residual finite state automata; minimal NFA
© EDP Sciences 2008