| 基于子集构造法的优化的NFA确定化算法 |
| |
| 引用本文： | 任平红,陈矗,曹宝香,禹继国.基于子集构造法的优化的NFA确定化算法[J].计算机技术与发展,2011,21(1). |
| |
| 作者姓名： | 任平红 陈矗 曹宝香 禹继国 |
| |
| 作者单位： | 山东曲阜师范大学计算机科学学院,山东,日照,276826 |
| |
| 基金项目： | 山东省优秀中青年科学家奖励基金 |
| |
| 摘 要： | 使用子集构造法对非确定有限自动机进行确定化的过程中存在大量重复计算的问题.为解决此问题,基于非确定有限自动机的特点并针对子集构造法的不足,提出了一种优化的非确定有限自动机确定化算法.首先定义了识别符的有效引出状态集概念并证明了ε-closure的并定理以保证算法的正确性,其次给出了用于避免重复计算的识别符的有效引出状态集的构造子算法和单状态集的ε-closure的求算子算法,基于这两个子算法给出了优化的非确定有限自动机确定化算法,最后将算法应用于实例,实验结果表明计算量远小于子集构造法的计算量.相比子集构造法,算法能更有效地对非确定有限自动机进行确定化.
|
| 关 键 词： | 子集构造法 非确定有限自动机 优化的 确定化算法 |
An Optimized Algorithm for Transition from NFA to DFA Based on Subset Construction Method |
| |
| REN Ping-hong,CHEN Chu,CAO Bao-xiang,YU Ji-guo.An Optimized Algorithm for Transition from NFA to DFA Based on Subset Construction Method[J].Computer Technology and Development,2011,21(1). |
| |
| Authors: | REN Ping-hong CHEN Chu CAO Bao-xiang YU Ji-guo |
| |
| Abstract: | |
| |
| Keywords: | |
| 本文献已被 万方数据 等数据库收录！ |
|
