✦ LIBER ✦

A lower bound on the size of ε-free NFA corresponding to a regular expression

✍ Scribed by Yuri Lifshits

Publisher: Elsevier Science
Year: 2003
Tongue: English
Weight: 110 KB
Volume: 85
Category: Article
ISSN: 0020-0190
DOI: 10.1016/s0020-0190(02)00436-2

No coin nor oath required. For personal study only.

✦ Synopsis

Hromkovic et al. showed how to transform a regular expression of size n into an ε-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 lower bound (n log(n)) on the number of transitions. We improve the lower bound to ( n log 2 n log log n ).