Translating Regular Expressions into Small ε-Free Nondeterministic Finite Automata

Abstract

We prove that every regular expression of size n can be converted into an equivalent nondeterministic ε-free finite automaton (NFA) with $\text{O}$(n(log n)²) transitions in time $\text{O}$(n² log n). The best previously known conversions result in NFAs of worst-case size Θ(n²). We complement our result by proving an almost matching lower bound. We exhibit a sequence of regular expressions of size $\text{O}$(n) and show the number of transitions required in equivalent NFAs is Ω(n log n). This also proves there does not exist a linear-size conversion from regular expressions to NFAs.