Translation of binary regular expressions into nondeterministic ε-free automata with O(n log n) transitions

摘要

We show that every regular expression of size n over a fixed alphabet of s symbols can be converted into a nondeterministic ε-free finite-state automaton with O(snlogn) transitions (edges). In case of binary regular languages, this improves the previous known conversion from O(n(logn)2) transitions to O(nlogn). For the general case with no bound on cardinality of the input alphabet, our conversion yields a better constant factor in the O(n(logn)2) term. The number of states is bounded by O(n).