Translating regular expressions into small epsilon-free nondeterministic finite automata

We prove that every regular expression of size n can be converted into an e quivalent nondeterministic epsilon -free finite automaton (NFA) with C(n lo g n(2) ) transitions in time C(n(2) log n). The best previously known conve rsions result in NFAs of worst-case size Theta (n(2)). We complement our re sult by proving an almost matching lower bound. We exhibit a sequence of re gular expressions of size C(n) and show the number of transitions requited in equivalent NFAs is Omega (n log n). This also proves there does not exis t a linear-size conversion From regular expressions to NFAs. (C) 2001 Acade mic Press.