Conversion of regular expressions into realtime automata

Geffert, Viliam ; Ištoňová, L'ubomíra

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 40 (2006) no. 4, pp. 611-629

Résumé

We consider conversions of regular expressions into $k$-realtime finite state automata, i.e., automata in which the number of consecutive uses of $\epsilon$-transitions, along any computation path, is bounded by a fixed constant $k$. For $2$-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 $O\left(n\right)$ states, $O(nlogn)$ $\epsilon$-transitions, and $O\left(n\right)$ alphabet-transitions. We also show how to easily transform these $2$-realtime machines into $1$-realtime automata, still with only $O(nlogn)$ edges. These results contrast with the known lower bound $\Omega (n{(logn)}^2/loglogn)$, holding for $0$-realtime automata, i.e., for automata with no $\epsilon$-transitions.

Détail

DOI : 10.1051/ita:2006036

Classification : 68Q45
Keywords: descriptional complexity, finite-state automata, regular expressions