Conversion of regular expressions into realtime automata
Department of Computer Science, P. J. Šafárik University, Jesenná 5, 04001 Košice, Slovakia;
Accepted: 9 March 2006
We consider conversions of regular expressions into k-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 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(n) states, O(nlogn) ε-transitions, and O(n) 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 Ω(n(logn)2 / loglogn), holding for 0-realtime automata, i.e., for automata with no ε-transitions.
Mathematics Subject Classification: 68Q45
Key words: Descriptional complexity / finite-state automata / regular expressions.
© EDP Sciences, 2006