A simple way to construct NFA with fewer states and transitions

ABSTRACT

The problem of converting a regular expression to NFA is a fundamental problem that has been well studied. However, the two basic construction algorithms: (1) Thompson, (2) McNaughton-Yamada and Glushkov, does not yield the best solution in terms of the number of states and transitions. In this paper, we show: For a regular expression with l literals, we can construct an NFA with 2l states and 4l transitions in the worst case. Our algorithm runs in linear time with respect to the length of the regular expression. This improves the construction algorithm given by Chang in [5], which constructs an NFA with 5l=2 states and (10l -- 5)/2 transitions in the worst case. The method presented here is much simpler and easier to understand, as we use only naive ideas: divide and conquer.

REFERENCES

• 1: A. Aho. Pattern matching in strings. In Formal Language Theory(R. Book ed). Academic Press, 1980.
• 2: Valentin Antimirov, Partial derivatives of regular expressions and finite automaton constructions, Theoretical Computer Science, v.155 n.2, p.291-319, March 11, 1996 [doi>10.1016/0304-3975(95)00182-4]
• 3: Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
• 4: G. Berry , R. Sethi, From regular expressions to deterministic automata, Theoretical Computer Science, v.48 n.1, p.117-126, Dec., 1986
• 5: C. Chang. Ph.D Thesis. Department of Computer Science, Courant Institute, New York, 1992.
• 6: Charles L. A. Clarke , Gordon V. Cormack, On the use of regular expressions for searching text, ACM Transactions on Programming Languages and Systems (TOPLAS), v.19 n.3, p.413-426, May 1997 [doi>10.1145/256167.256174]
• 7: V. Glushkov. The abstract theory of automata. Russian Math. Surveys, 16:1--53, 1961.
• 8: P. P. G. Apostolopoulos, V. Peris. L5: A self learning layer 5 switch. In Technical Report RC21461. IBM, T.J. Watson Research Center, 1999.
• 9: R. McNaughton and H. Yamada. Regular expressions and state graphs for automata. Trans. IRS, EC(9):39--47, 1960.
• 10: Gene Myers, A Four Russians algorithm for regular expression pattern matching, Journal of the ACM (JACM), v.39 n.2, p.432-448, April 1992 [doi>10.1145/128749.128755]
• 11: Ken Thompson, Programming Techniques: Regular expression search algorithm, Communications of the ACM, v.11 n.6, p.419-422, June 1968 [doi>10.1145/363347.363387]