We consider conversions of regular expressions into -realtime finite state automata, i.e., automata in which the number of consecutive uses of -transitions, along any computation path, is bounded by a fixed constant . For -realtime automata, i.e., for automata that cannot change the state, without reading an input symbol, more than two times in a row, we show that the conversion of a regular expression into such an automaton produces only states, -transitions, and alphabet-transitions. We also show how to easily transform these -realtime machines into -realtime automata, still with only edges. These results contrast with the known lower bound , holding for -realtime automata, i.e., for automata with no -transitions.
Mots-clés : descriptional complexity, finite-state automata, regular expressions
@article{ITA_2006__40_4_611_0, author = {Geffert, Viliam and I\v{s}to\v{n}ov\'a, L'ubom{\'\i}ra}, title = {Conversion of regular expressions into realtime automata}, journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications}, pages = {611--629}, publisher = {EDP-Sciences}, volume = {40}, number = {4}, year = {2006}, doi = {10.1051/ita:2006036}, zbl = {1110.68063}, language = {en}, url = {http://archive.numdam.org/articles/10.1051/ita:2006036/} }
TY - JOUR AU - Geffert, Viliam AU - Ištoňová, L'ubomíra TI - Conversion of regular expressions into realtime automata JO - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications PY - 2006 SP - 611 EP - 629 VL - 40 IS - 4 PB - EDP-Sciences UR - http://archive.numdam.org/articles/10.1051/ita:2006036/ DO - 10.1051/ita:2006036 LA - en ID - ITA_2006__40_4_611_0 ER -
%0 Journal Article %A Geffert, Viliam %A Ištoňová, L'ubomíra %T Conversion of regular expressions into realtime automata %J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications %D 2006 %P 611-629 %V 40 %N 4 %I EDP-Sciences %U http://archive.numdam.org/articles/10.1051/ita:2006036/ %R 10.1051/ita:2006036 %G en %F ITA_2006__40_4_611_0
Geffert, Viliam; Ištoňová, L'ubomíra. Conversion of regular expressions into realtime automata. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 40 (2006) no. 4, pp. 611-629. doi : 10.1051/ita:2006036. http://archive.numdam.org/articles/10.1051/ita:2006036/
[1] Complexity measures for regular expressions. J. Comput. Syst. Sci. 12 (1976) 134-46. | Zbl
and ,[2] Translation of binary regular expressions into nondeterministic -free automata with transitions. J. Comput. Syst. Sci. 67 (2003) 451-72. | Zbl
,[3] Algebraic and Automata-Theoretic Properties of Formal Languages. North-Holland (1975). | MR | Zbl
,[4] Introduction to Automata Theory, Languages, and Computation. Addison-Wesley (1979). | MR | Zbl
and ,[5] Translating regular expressions into small -free nondeterministic automata, in Proc. Symp. Theoret. Aspects Comput. Sci. Lect. Notes Comput. Sci. 1200 (1997) 55-66. | Zbl
, and ,[6] Translating regular expressions into small -free nondeterministic finite automata. J. Comput. Syst. Sci. 62 (2001) 565-88. | Zbl
, and ,[7] A lower bound on the size of -free NFA corresponding to a regular expression. Inform. Process. Lett. 85 (2003) 293-99.
,[8] Parsing Theory, Vol. I: Languages and Parsing. EATCS Monographs in Theoret. Comput. Sci. 15 (1988). | MR | Zbl
and ,Cité par Sources :