基于子集构造法的优化的NFA确定化算法

摘要：

使用子集构造法对非确定有限自动机进行确定化的过程中存在大量重复计算的问题.为解决此问题,基于非确定有限自动机的特点并针对子集构造法的不足,提出了一种优化的非确定有限自动机确定化算法.首先定义了识别符的有效引出状态集概念并证明了ε-closure的并定理以保证算法的正确性,其次给出了用于避免重复计算的识别符的有效引出状态集的构造子算法和单状态集的ε-closure的求算子算法,基于这两个子算法给出了优化的非确定有限自动机确定化算法,最后将算法应用于实例,实验结果表明计算量远小于子集构造法的计算量.相比子集构造法,算法能更有效地对非确定有限自动机进行确定化.

关键词：子集构造法、非确定有限自动机、优化的、确定化算法

所属期刊栏目：21

分类号：TP301.1(计算技术、计算机技术)

资助基金：山东省优秀中青年科学家奖励基金2005BS01016

在线出版日期：2011-05-30（万方平台首次上网日期，不代表论文的发表时间）

页数：共4页

页码：70-73