东北大学学报（自然科学版）

东北大学学报(自然科学版) ›› 2012, Vol. 33 ›› Issue (4): 482-485.DOI: -

• 论著 • 上一篇    下一篇

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

敬茂华;李国瑞;史闻博;才书训;   

  1. 东北大学秦皇岛分校电子信息系;
  • 收稿日期:2013-06-19 修回日期:2013-06-19 发布日期:2013-04-04
  • 通讯作者: -
  • 作者简介:-
  • 基金资助:
    教育部基本科研业务费专项资金资助项目((N100323001)

Improved conversion algorithm from NFA to DFA

Jing, Mao-Hua (1); Li, Guo-Rui (1); Shi, Wen-Bo (1); Cai, Shu-Xun (1)   

  1. (1) Electronic Information Department, Northeastern University at Qinhuangdao, Qinhuangdao 066004, China
  • Received:2013-06-19 Revised:2013-06-19 Published:2013-04-04
  • Contact: Jing, M.-H.
  • About author:-
  • Supported by:
    -

RichHTML

0

PDF (PC)

907

摘要： 研究了不确定的有限自动机转换为与之等价的确定的有限自动机的算法机制和复杂性,以及传统的子集算法在转换过程中存在的大量重复遍历和无效遍历现象,并针对上述现象提出了一种改进的子集法算法MF-SUBSET.结果表明,MF-SUBSET算法通过增加状态标志和遍历路径标志来决定当前的搜索策略,能够有效地避免转换过程中的重复遍历和无效遍历操作,极大地提高了转换效率.

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

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.

中图分类号: