| 一种改进的从NFA到DFA的转换算法 |
| |
| 引用本文： | 敬茂华,李国瑞,史闻博,才书训.一种改进的从NFA到DFA的转换算法[J].东北大学学报(自然科学版),2012,33(4):482-485. |
| |
| 作者姓名： | 敬茂华 李国瑞 史闻博 才书训 |
| |
| 作者单位： | 东北大学秦皇岛分校电子信息系,河北秦皇岛,066004 |
| |
| 基金项目： | 教育部基本科研业务费专项资金资助项目( |
| |
| 摘 要： | 研究了不确定的有限自动机转换为与之等价的确定的有限自动机的算法机制和复杂性,以及传统的子集算法在转换过程中存在的大量重复遍历和无效遍历现象,并针对上述现象提出了一种改进的子集法算法MF-SUBSET.结果表明,MF-SUBSET算法通过增加状态标志和遍历路径标志来决定当前的搜索策略,能够有效地避免转换过程中的重复遍历和无效遍历操作,极大地提高了转换效率.
|
| 关 键 词： | 有限自动机 转换 子集法 MF子集法 搜索策略 |
Improved Conversion Algorithm from NFA to DFA |
| |
| JING Mao-hua,LI Guo-rui,SHI Wen-bo,CAI Shu-xun.Improved Conversion Algorithm from NFA to DFA[J].Journal of Northeastern University(Natural Science),2012,33(4):482-485. |
| |
| Authors: | JING Mao-hua LI Guo-rui SHI Wen-bo CAI Shu-xun |
| |
| Institution: | (Electronic Information Department,Northeastern University at Qinghuangdao,Qinghuangdao 066004,China.) |
| |
| Abstract: | 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. |
| |
| Keywords: | finite automata conversion SUBSET MF-SUBSET search strategy |
| 本文献已被 CNKI 万方数据 等数据库收录！ |
| 点击此处可从《东北大学学报(自然科学版)》浏览原始摘要信息 |
| 点击此处可从《东北大学学报(自然科学版)》下载免费的PDF全文 |
