一种改进的从NFA到DFA的转换算法  

Improved Conversion Algorithm from NFA to DFA

作　　者：敬茂华[1] 李国瑞[1] 史闻博[1] 才书训[1] 

机构地区：[1]东北大学秦皇岛分校电子信息系,河北秦皇岛066004

出　　处：《东北大学学报（自然科学版）》2012年第4期482-485,共4页Journal of Northeastern University(Natural Science)

基　　金：教育部基本科研业务费专项资金资助项目((N100323001)

摘　　要：研究了不确定的有限自动机转换为与之等价的确定的有限自动机的算法机制和复杂性,以及传统的子集算法在转换过程中存在的大量重复遍历和无效遍历现象,并针对上述现象提出了一种改进的子集法算法MF-SUBSET.结果表明,MF-SUBSET算法通过增加状态标志和遍历路径标志来决定当前的搜索策略,能够有效地避免转换过程中的重复遍历和无效遍历操作,极大地提高了转换效率.The mechanism and complexity of the conversion algorithm from nondeterministic finite automata（NFA） to deterministic finite automata（DFA） were studied,and a great number of repeated traversal and invalid traversal phenomenon in the well known SUBSET algorithm were especially studied.An improved MF-SUBSET algorithm was proposed to solve the above problem.The simulation results indicated that the present searching strategy could be decided by the proposed MF-SUBSET algorithm through increasing status flags and traversal path flags,which could obviously avoid the repeated traversal and invalid traversal operation and effectively improve the conversion efficiency.

关 键 词：有限自动机 转换 子集法 MF子集法 搜索策略 

分 类 号：TP301.1[自动化与计算机技术—计算机系统结构]