基于子集构造法的优化的NFA确定化算法-《计算机技术与发展》

文章信息/Info

Title:: An Optimized Algorithm for Transition from NFA to DFA Based on Subset Construction Method

Author(s):: PEN Ping-hong; CHEN Chu; CAO Bao-xiang; YU Ji-guo; College of Computer Science, Qufu Normal University

Keywords:: subset construction method; non-deterministic finite automata; optimized; algorithm for transition from NFA to DFA

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

Abstract:: The problem of repetitive computing exits in the process of transition from non-deterministic finite automata to deterministic finite automata using the subset construction method. To solve this problem, an optimized algorithm for transition from NFA to DFA is put forward on the basis of characters of NFA and according to shortcomings of the subset.construction method. First, the concept that effective source state set for a mark symbol is defined and the theorem that combination of ε -closure is proved. The theorem guarantees the rightness of the following algorithms. Second, two sub algorithms that construction of effective source state set for a mark symbol and that computing ε -closure of a set with only one state are given. Based on these sub algorithms, the optimized algorithm for transition from NFA to DFA is given. In the end, an experiment is carried out and the result shows that computing amount of this algorithm is far less than that of subset construction method. Comparing to subset construction method, this algorithm can convert NFA to DFA more efficiently