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

• 作者: 任平红 曹宝香 禹继国 陈矗
• 来源期刊: 计算机技术与发展
• 学科: 工学
• 关键词: 子集构造法 非确定有限自动机 优化的 确定化算法
• 年，卷（期）: 2011,（1）
• 所属期刊栏目: 智能、算法、系统工程
• 页码范围: 70-73
• 分类号: TP301.1
• 字数: 3493字
• 语种: 中文
• DOI: 10.3969/j.issn.1673-629X.2011.01.019

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	任平红	山东曲阜师范大学计算机科学学院	2	17	2.0	2.0
2	陈矗	山东曲阜师范大学计算机科学学院	2	17	2.0	2.0
3	曹宝香	山东曲阜师范大学计算机科学学院	2	9	1.0	2.0
4	禹继国	山东曲阜师范大学计算机科学学院	1	9	1.0	1.0