Follow automata

We give two new algorithms for constructing small nondeterministic finite automata (NFA) from regular expressions. The first constructs NFAs with epsilon-transitions (epsilonNFA) which are smaller than all the other epsilonNFAs obtained by similar constructions. Their size is at most 3/2\alpha\ + 5/2, where alpha is the regular expression. This is very close to optimal since we prove also the lower bound 4/3\alpha\ + 5/2. The second constructs NFAs. It uses epsilon-elimination in the epsilonNFAs we just introduced and builds a quotient of the well-known position automaton w.r.t. the equivalence given by the follow relation; therefore giving the name of follow automaton. The new automaton uses optimally the information from the positions of a regular expression. We compare the follow automaton with the best constructions to date and show that it has important advantages over those. (C) 2003 Elsevier Science (USA). All rights reserved.