摘要
使用子集构造法对非确定有限自动机进行确定化的过程中存在大量重复计算的问题。为解决此问题,基于非确定有限自动机的特点并针对子集构造法的不足,提出了一种优化的非确定有限自动机确定化算法。首先定义了识别符的有效引出状态集概念并证明了ε-closure的并定理以保证算法的正确性,其次给出了用于避免重复计算的识别符的有效引出状态集的构造子算法和单状态集的ε-closure的求算子算法,基于这两个子算法给出了优化的非确定有限自动机确定化算法,最后将算法应用于实例,实验结果表明计算量远小于子集构造法的计算量。相比子集构造法,算法能更有效地对非确定有限自动机进行确定化。
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.
出处
《计算机技术与发展》
2011年第1期70-73,共4页
Computer Technology and Development
基金
山东省优秀中青年科学家奖励基金(2005BS01016)
关键词
子集构造法
非确定有限自动机
优化的
确定化算法
subset construction method
non-deterministic finite automata
optimized
algorithm for transition from NFA to DFA
