Translating Regular Expressions into Small ε-Free Nondeterministic Finite Automata

✍ Scribed by Juraj Hromkovič; Sebastian Seibert; Thomas Wilke

• Publisher: Elsevier Science
• Year: 2001
• Tongue: English
• Weight: 252 KB
• Volume: 62
• Category: Article
• ISSN: 0022-0000
• DOI: 10.1006/jcss.2001.1748

✦ Synopsis

We prove that every regular expression of size n can be converted into an equivalent nondeterministic =-free finite automaton (NFA) with O(n(log n) 2 ) transitions in time O(n 2 log n). The best previously known conversions result in NFAs of worst-case size 3(n 2 ). We complement our result by proving an almost matching lower bound. We exhibit a sequence of regular expressions of size O(n) and show the number of transitions required in equivalent NFAs is 0(n log n). This also proves there does not exist a linear-size conversion from regular expressions to NFAs.