| 构造正则表达式的Follow自动机并行算法研究 |
| |
| 引用本文： | 杨瑞敏,任冰.构造正则表达式的Follow自动机并行算法研究[J].中原工学院学报,2010,21(1):64-67,71. |
| |
| 作者姓名： | 杨瑞敏 任冰 |
| |
| 作者单位： | 1. 中原工学院
2. 河南工业大学,设计艺术学院,郑州,450007 |
| |
| 摘 要： | 给出了一种从正则表达式到Follow自动机的并行化算法. 先构造正则表达式的Thompson自动机, 再对其消除ξ边,实现Thompson自动机到Glushkov自动机的转换, 然后对Glushkov自动机的等价状态进行合并,从而得到一种规模更小的有限自动机,即Follow自动机,最后以实例模拟其并行转化过程.
|
| 关 键 词： | 有限自动机 状态 正则表达式 并行化 |
Parallel Algorithms for Constructing Follow Automata of Regular Expressions |
| |
| YANG Rui-min,REN Bing.Parallel Algorithms for Constructing Follow Automata of Regular Expressions[J].Journal of Zhongyuan Institute of Technology,2010,21(1):64-67,71. |
| |
| Authors: | YANG Rui-min REN Bing |
| |
| Affiliation: | YANG Rui-min1,REN Bing2(1.Zhongyuan University of Technology,2.Henan University of Technology,Zhengzhou 450007,China) |
| |
| Abstract: | 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. |
| |
| Keywords: | NFA state regular expressions parallel algorithm follow automata |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
|
