一类NFA到DFA的直接转化方法

• 作者: 程元斌
• 来源期刊: 计算机系统应用
• 关键词: 有限自动机 非确定性有限自动机 确定性有限自动机 子集构造法 直接转换法
• 年，卷（期）: 2012,（10）
• 页码范围: 109-113
• 字数: 3583字
• 语种: 中文

摘要

NFA 的确定化具有重要的理论和实际意义.迄今为止,普遍采用子集构造法将一个 NFA(非确定性自动机)转化为 DFA(确定性自动机),但这种方法需要引入空输入ε及状态子集 I 的ε-闭包,其计算过程相对繁琐.而且在确定化过程中对于 NFA状态集存在ε-closure重复计算和由于对非ε转换的判断而引起的重复计算等问题.本文描述了一种将一类NFA直接转化为DFA的方法.在本方法中,不需要引入空输入ε,可根据原始的NFA状态图或状态转移表直接得出等价的 DFA 状态图或状态转移表,而且所有状态都是单一的状态而非集合状态,便于软硬件实现与测试.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	程元斌	江汉大学数学与计算机科学学院	8	13	2.0	3.0