Reducing NFAs by invariant equivalences
We give new general methods for constructing small non-deterministic finite automata (NFA) from arbitrary ones. Given an NFA, we compute the largest right-invariant equivalence on the set of states and then merge the equivalent states to obtain a smaller automaton. When applying this method to position automata, we get a way to convert regular expressions into NFAs which are always smaller than or equal to the position, partial derivative, and follow automata; it can be arbitrarily smaller. The construction can be dually made for left-invariant equivalences and then the two can be combined for even better results. (C) 2003 Elsevier B.V. All rights reserved.
invariant equivalences non-deterministic finite automata regular expressions automata minimization derivatives of regular expressions