Minimized Thompson NFA

Abstract

The problem of converting a regular expression to nondeterministic finite automaton (NFA) is a fundamental problem that has been well studied. However, the two basic construction algorithms: (1) Thompson, (2) McNaughton–Yamada and Glushkov, both have disadvantages. In this article: first, a ‘smart’ parsing algorithm is developed which constructs a parse tree with at most (3l − 1) nodes form a regular expression with l literals; second, we propose an algorithm that works on the resulting NFA from Thompson's construction, eliminating as many auxiliary states as possible while maintaining Thompson's properties. It is shown that the resulting NFA is minimized. This means that no auxiliary states can be eliminated without violating the defining properties of Thompson NFA. The time and space requirements for the above algorithms are linear with respect to the length of the regular expression.

Keywords:

• Regular expression
• NFA
• Minimization
• Topological sorting

Acknowledgements

The author would like to thank Dr. Rodney Canfield for many helpful discussions about this work. I would also like to thank members of Cisco Local Director Group, especially Curt Cursey, Bruce Wong and Justin Pecqueur for their valuable comments, where I was an Intern.