Special Issue: Descriptional Complexity of Formal Systems (DCFS '04)No Access

MINIMALIZATIONS OF NFA USING THE UNIVERSAL AUTOMATON

LIBOR POLÁK

Department of Mathematics, Masaryk University, Janáckovo nám. 2a, 662 95 Brno, Czech Republic

Supported by the Ministry of Education of the Czech Republic under the projects MSM 143100009 and 0021622409, and partially also by Project AKTION Österreich – Tschechische Republik.

Search for more papers by this author

https://doi.org/10.1142/S0129054105003431Cited by:22 (Source: Crossref)

Abstract

As is well known, each minimal NFA for a regular language L is isomorphic to a subautomaton of the so-called universal automaton for L. We explore and compare various conditions on sets of states of which are related to the fact that induced subautomata of accept the whole language L. The methods of several previous works on minimalizations of NFA can be modified so that they fit in our approach. We also propose a new algorithm which is easy to implement.

Keywords:

AMSC: 68Q45 Formal languages and automata

References

A. Arnold, A. Dicky and M. Nivat, Bull. EATCS 47, 166 (1992). Google Scholar
J. A. Brzozowski, Canonical regular expressions and minimal state graphs for definitive events, Proc. Symp. on Math. Theory of Automata (Brooklyn Polytechnic Institute, 1963) pp. 529–561. Google Scholar
Carrez, C.; On the minimalization of non-deterministic automaton, Laboratoire de Calcul de la Faculté des Sciences de l'Université de Lille, 1970 . Google Scholar
J. H. Conway , Regular Algebra and Finite Machines ( Chapman and Hall, Ltd. , 1971 ) . Google Scholar
F. Denis, A. Lemay and A. Terlutte, Fundam. Inform. 51(4), 339 (2002). Web of Science, Google Scholar
Tao Jiang and B. Ravikumar, Inf. Process. Lett. 40(1), 25 (1991). Crossref, Web of Science, Google Scholar
T. Kameda and P. Weiner, IEEE Transactions on Computers C-19(7), 617 (1970). Crossref, Web of Science, Google Scholar
S. Lombardy, On the construction of reversible automata for reversible languages, Lecture Notes in Computer Science, Vol. 2380 (Springer, 2002) pp. 170–182. Google Scholar
O. Matz and A. Potthoff, Computing small nondeterministic finite automata, Proc. Workshop on Tools and Algorithms for the Construction and Analysis of Systems 1995, BRICS Lecture Notes (1995) pp. 74–88. Google Scholar
L. Polák, Syntactic semiring and universal automaton, Proc. Developments in Language Theory, Lecture Notes in Computer Science, Vol. 2710 (Springer, 2003) pp. 411–422. Google Scholar
J. Sakarovitch , Éléments de théorie des automates ( Vuibert , 2003 ) . Google Scholar
H. Tamm and E. Ukkonen, Bideterministic automata and minimal representations of regular languages, Proc. of the Eight International Conference on Implementation and Application of Automata, Lecture Notes in Computer Science, Vol. 2759 (Springer, 2003) pp. 61–71. Google Scholar