inria-00296658, version 1
Minimal NFA and biRFSA Languages
Michel Latteux
a, 1Yves Roos
a, 1, 2Alain Terlutte b, 1, 2
RAIRO - Theoretical Informatics and Applications 43, 2 (2009) 221-237
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.
- a – Université des Sciences et Technologies de Lille - Lille I
- b – Université Charles de Gaulle - Lille III
- 1: Laboratoire d'Informatique Fondamentale de Lille (LIFL)
- CNRS : UMR8022 – INRIA – IRCICA – Université des Sciences et Technologies de Lille - Lille I
- 2: MOSTRARE (INRIA Lille - Nord Europe)
- INRIA – CNRS : UMR8022 – Université des Sciences et Technologies de Lille - Lille I : EA3588 – Université Charles de Gaulle - Lille III
- Domain : Computer Science/Learning
- Keywords : Residual finite state automata – minimal NFA
- inria-00296658, version 1
- http://hal.inria.fr/inria-00296658
- oai:hal.inria.fr:inria-00296658
- From: Yves Roos
- Submitted on: Tuesday, 15 July 2008 08:45:32
- Updated on: Friday, 30 October 2009 08:42:40
Associated documents
Export