Parallel Algorithms for Constructing Fellow Automata of Regular Expressions

摘要

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.