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.