Tytuł artykułu
Autorzy
Wybrane pełne teksty z tego czasopisma
Identyfikatory
Warianty tytułu
Języki publikacji
Abstrakty
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(En) 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(En) 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(log2 n)2 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(En).
Słowa kluczowe
Wydawca
Czasopismo
Rocznik
Tom
Strony
79--94
Opis fizyczny
Bibliogr. 10 poz., rys., tab.
Twórcy
autor
- LACL, EA 4912, Université Paris-Est Créteil (UPEC), Créteil, France
autor
- LMRS, UMR 6085 CNRS, Normandie Université, Rouen, France
autor
- 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.
Typ dokumentu
Bibliografia
Identyfikator YADDA
bwmeta1.element.baztech-6b47ed3a-6653-404c-b114-467a937add66