A lower bound on the size of epsilon-free NFA corresponding to a regular expression
Hromkovic et al. showed how to transform a regular expression of size n into an epsilon-free nondeterministic finite automaton (which defines the same language as the expression) with O(n) states and O(n log(2)(n)) transitions. They also established a Omega(n log(n)) on the number of transitions. We improve the lower bound to Omega(n log2 n/log log n). (C) 2002 Elsevier Science B.V. All rights reserved.
regular expressions formal languages combinatorial problems epsilon-free nondeterministic automata