Constructing NFAs by Optimal Use of Positions in Regular Expressions

We give two new algorithms for constructing small nondeterministic finite automata (NFA) from regular expressions. The first constructs NFAs with ε-moves (εNFA) which are smaller than all the other εNFAs obtained by similar constructions. Their size is at most 3/2|α| + 5/2, where α is the regular expression. The second constructs NFAs. It uses ε-elimination in the εNFAs we just introduced and builds a quotient of the well-known position automaton. Our NFA is always smaller and faster to compute than the position automaton. It uses optimally the information from the positions of a regular expression.