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.