Finite State Automata from Regular Expression Trees

Thompson [13] introduced an innovative method for obtaining non-deterministic finite state automata (nfa) from regular expression. His formulation of nfas makes use of s-transitions (null symbol input) and requires in the worst case 2σ+2 OPS states, where σ is the number of occurencies of alphabet symbols and OPS is the number of operands in the original regular expression. We modify this algorithm to obtain a nfa M without e-transitions that has in the worst case σ+1 states. Using multi-branch expression trees to store the regular expressions efficiently, the algorithm presented here is directly parallelizable. The algorithm necessitates that we maintain a finite state automata which had no e-transition and has a starting node of zero in-degree