Comparing the size of NFAs with and without ε-transitions

AbstractThe construction of an ε-free nondeterministic finite automaton (NFA) from a given NFA is a basic step in the development of compilers and computer systems. The standard conversion may produce an ε-free NFA with up to Ω(n2⋅|Σ|) transitions for an NFA with n states and alphabet Σ. To determine the largest asymptotic gap between the minimal number of transitions of NFAs and their equivalent ε-free NFAs has been a longstanding open problem. We show that there exist regular languages Ln that can be recognized by NFAs with O(nlog2n) transitions, but ε-free NFAs need Ω(n2) transitions to accept Ln. Hence the standard conversion cannot be improved drastically. However, Ln requires an alphabet of size n, but we also construct regular languages Kn over {0,1} with NFAs of size O(nlog2n), whereas ε-free NFAs require size n⋅2c⋅log2n for every c