Parallel Algorithms for Constructing Fellow Automata of Regular Expressions
Sun Yuqiang, Yang Ruimin, Yuwan Gu, You Jing · 2009
A parallel algorithm for translating regular expression into its Follow automata is proposed in the paper. Firstly, we construct the Thompson automata of a regular expression. Then, the Glushkov automata are achieved by removing xi the path and the equivalent states which have equivalent relations are merged into one. So we can get a smaller finite automata, named Follow automata. Finally the parallel processing of algorithm is described in detail with an example.