构造正则表达式的Follow自动机并行算法研究  

Parallel Algorithms for Constructing Follow Automata of Regular Expressions

作　　者：杨瑞敏[1] 任冰[2] 

机构地区：[1]中原工学院 [2]河南工业大学设计艺术学院,郑州450007

出　　处：《中原工学院学报》2010年第1期64-67,71,共5页Journal of Zhongyuan University of Technology

摘　　要：给出了一种从正则表达式到Follow自动机的并行化算法.先构造正则表达式的Thompson自动机,再对其消除ξ边,实现Thompson自动机到Glushkov自动机的转换,然后对Glushkov自动机的等价状态进行合并,从而得到一种规模更小的有限自动机,即Follow自动机,最后以实例模拟其并行转化过程.A parallel algorithm for translating regular expression into its follow automata is proposed in the paper.Firstly,Thompson automata of a regular expression is cousfructed.Then,the Glushkov automata is achieved by removing the path and the equivalent states which have equivalent relations merged into one.So the smaller finite automata,named follow automata is gotten.Finally the parallel processing of algorithm is described in detail with an example.

关 键 词：有限自动机 状态 正则表达式 并行化 

分 类 号：TP391[自动化与计算机技术—计算机应用技术]