Computing -free NFA from regular expressions in time
Computing -Free NFA from Regular Expressions in ( log()) Time
The standard procedure to transform a regular expression of size to an -free nondeterministic finite automaton yields automata with states and ( ) transitions. For a long time this was supposed to be also the lower bound, but a result by Hromkovic showed how to build an -free NFA with only ( log()) transitions. The current lower bound on the number of transitions is Ω( log()). A rough running time estimation for the common follow sets (CFS) construction proposed by Hromkovič ...
Page 1