Reducing the size of NFAs by using equivalences and preorders

Abstract. The efficiency of regular expression matching algorithms depends very much on the size of the nondeterministic finite automata (NFA) obtained from regular expressions. Reducing the size of these automata by using equivalences has been shown to reduce significantly the search time. We consider the problem of reducing the size of arbitrary NFAs using equivalences and preorders. For equivalences, we give an algorithm to optimally combine equivalent states for reducing the size of the automata. We also show that the problem of optimally using preorders to reduce the size of an automaton is NP-hard