On the Transition Reduction Problem for Finite Automata

• Autorzy: Dahmoune M. , Abdalaoui E. H. , Ziadi D.

Identyfikatory

DOI

10.3233/FI-2014-1033

• Języki publikacji: EN

Abstrakty

EN

In this paper we apply the concept of common follow sets (CFS) of a regular expression to homogeneous finite state automaton. Based on this concept and using particular binary trees, we devise an efficient algorithm to reduce (minimize) the number of transitions of the automaton recognizing the language L(E_n) denoted by the regular expression En= (1 + ε) · (2 + ε) · (3 + ε) · · · (n+ε). Experiments reveal that for small values of n, all ε –free NFAs with n+1 states and with a minimum number of transitions for L(E_n) are exactly those obtained by our construction. Also, the produced ε-free NFA is asymptotically minimal, in the sense that the number of transitions is equivalent to n(log₂ n)² which corresponds in the same time to the upper and the lower bound. We conjecture that our construction is not only a reduction but a minimization for L(E_n).

Słowa kluczowe

EN

automata; transition; tree; reduction; minimization

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2014
• Tom: Vol. 132, nr 1
• Strony: 79--94
• Opis fizyczny: Bibliogr. 10 poz., rys., tab.

Twórcy

autor

Dahmoune M.

• LACL, EA 4912, Université Paris-Est Créteil (UPEC), Créteil, France

autor

Abdalaoui E. H.

• LMRS, UMR 6085 CNRS, Normandie Université, Rouen, France

autor

Ziadi D.

• LITIS, EA 4108, Normandie Université, Rouen, France

Bibliografia

• [1] Jean-Marc Champarnaud, Faissal Ouardi, and Djelloul Ziadi. An efficient computation of the equation K-automaton of a regular K-expression. Fundam. Inf, 90(1-2): 1–16, 2009.
• [2] Russ Cox. Minimal number of edges in ε-free non-deterministic finite automata (NFA) for regular expression (1 + ε) • (2 + ε) • (3 + ε) • • • (n + ε). The On-Line Encyclopedia of Integer Sequences. Sequence A129403, 2007.
• [3] Viliam Geffert. Translation of binary regular expressions into nondeterministic ε -free automata with transitions. J. Comput. Syst. Sci., 66(3): 451–472, 2003.
• [4] Christian Hagenah and Anca Muscholl. Computing ε -free NFA from regular expressions in O(n log2(n)) time. RAIRO - Theoretical Informatics and Applications, 34(4): 257–277, 2000.
• [5] John Hopcroft. An n log n algorithm for minimizing states in a finite automaton. In Z. Kohavi and A. Paz, editors, Theory of Machines and Computations, pages 189–196. Academic Press, New York, 1971.
• [6] Juraj Hromkovič, Sebastian Seibert, and Thomas Wilke. Translating regular expressions into small ε –free nondeterministic finite automata. J. Comput. Syst. Sci., 62(4): 565–588, 2001.
• [7] Yury Lifshits. A lower bound on the size of ε -free NFA corresponding to a regular expression. Inf. Process. Lett., 85(6): 293–299, 2003.
• [8] Edward F. Moore. Gedanken-experiments on sequential machines. In C. E. Shannon and J. McCarthy, editors, Automata Studies, volume 34, pages 129–153. Princeton University Press, Princeton, N. J., 1956.
• [9] Faissal Ouardi and Djelloul Ziadi. Efficient weighted expressions conversion. RAIRO - Theoretical Informatics and Applications, 42(2): 285–307, 2008.
• [10] Georg Schnitger. Regular expressions and NFAs without ε-transitions. In Bruno Durand and Wolfgang Thomas, editors, STACS, volume 3884 of Lecture Notes in Computer Science, pages 432–443, Springer, 2006.