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 ε-free finite automaton (NFA) with O(n(log n)2) transitions in time O(n2 log n). The best previously known conversions result in NFAs of worst-case size Θ(n2). We complement our result by proving an almost matching lower bound. We exhibit a sequence of regular expressions of size 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.