Translating regular expressions into small ε-free nondeterministic finite automata

We prove that every regular expression of size n can be converted into an equivalent nondeterministic epsilon -free finite automaton (NFA) with C(n log n(2) ) transitions in time C(n(2) log n). The best previously known conversions result in NFAs of worst-case size Theta (n(2)). We complement our result by proving an almost matching lower bound. We exhibit a sequence of regular 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 exist a linear-size conversion From regular expressions to NFAs. (C) 2001 Academic Press.