We consider the problem of converting regular expressions of length
n over an alphabet of size
k into
ε-free NFAs with as few transitions as possible. Whereas the previously best construction uses
O(
n ·
min{
k,
log
2
n} ·
log
2
n) transitions, we show that
O(
n · log
22
k · log
2
n ) transitions suffice. For small alphabets we further improve the upper bound to
O(n ·log2 2k ·kLk (n)+1)O(n \cdot log_2 2k \cdot k^{L_k (n)+1}), where
L
k
(
n) =
O(log
2*_{\rm 2}^{\rm *}
n). In particular,
n ·2O(log*2 n)n \cdot 2^{O({log}^*_2 n)} transitions and hence almost linear size suffice for the binary alphabet! Finally we show the lower bound Ω(
n · log
22_{\rm 2}^{\rm 2} 2
k) and as a consequence the upper bound
O(
n · log
22_{\rm 2}^{\rm 2}
n) of [7] for general alphabets is best possible. Thus the conversion problem is solved for large alphabets (
k =
n
Ω(1)) and almost solved for small alphabets (
k =
O(1)).
Classification. Automata and formal languages, descriptional complexity, nondeterministic automata, regular expressions.