基于子集构造法的优化的NFA确定化算法
发布时间：2023-02-25 15:00:08 来源：文档文库
小
中
大
字号：
基于子集构造法的优化的NFA确定化算法
任平红;陈矗;曹宝香;禹继国
【摘 要】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.%使用子集构造法对非确定有限自动机进行确定化的过程中存在大量重复计算的问题.为解决此问题,基于非确定有限自动机的特点并针对子集构造法的不足,提出了一种优化的非确定有限自动机确定化算法.首先定义了识别符的有效引出状态集概念并证明了ε-closure的并定理以保证算法的正确性,其次给出了用于避免重复计算的识别符的有效引出状态集的构造子算法和单状态集的ε-closure的求算子算法,基于这两个子算法给出了优化的非确定有
限自动机确定化算法,最后将算法应用于实例,实验结果表明计算量远小于子集构造法的计算量.相比子集构造法,算法能更有效地对非确定有限自动机进行确定化. 【期刊名称】《计算机技术与发展》 【年(卷,期】2011(021001 【总页数】4页(P70-73
【关键词】子集构造法;非确定有限自动机;优化的;确定化算法 【作 者】任平红;陈矗;曹宝香;禹继国
【作者单位】山东曲阜师范大学计算机科学学院,山东,日照,276826;山东曲阜师范大学计算机科学学院,山东,日照,276826;山东曲阜师范大学计算机科学学院,山东,日照,276826;山东曲阜师范大学计算机科学学院,山东,日照,276826 【正文语种】中 文 【中图分类】TP301.1 0 引 言
作为计算机科学的基础,有限自动机(Finite Automata,FA可以抽象绝大多数计算机领域的有限系统,广泛应用于自然语言处理[1]和串匹配[2]等诸多方面。非确定有限自动机(Non-deterministic Finite Automata,NFA是FA理论的重要组成部分,NFA的化简[3,4]和确定化[5～8]具有重要的理论和实际意义。目前广为采用的子集构造法[9,10]虽然能够正确地完成NFA的确定化,但是在确定化过程中对于NFA状态集存在ε-closure重复计算和由于对非ε转换的判断而引起的重复计算等问题[5,8,9]。当 NFA状态集元素数量较多时重复计算的问题非常严重。为解决
此问题,提出一种基于子集构造法的优化的 NFA确定化算法,可以有效地避免重复计算的问题。
1 识别符的有效引出状态集概念和ε-closure并定理
为规整起见,首先给出NFA的一般定义并在全文中统一使用其定义中的符号。 定义1[11]:NFA定义为一个四元组:M=(Q,Σ, δ,q0,F。其中:Q是状态集,Σ是基本字母表,δ是状态转换函数(Q×(Σ∪{ε}→2Q,q0是开始状态,F是终态集。 基于NFA的定义,定义2给出识别符的有效引出状态集的定义。 定义2:对于识别符a(a∈Σ有效的引出状态集E[a]定义为:E[a]={q|q∈Q∧δ(q,a≠∅}。
识别符的有效引出状态集E[a]指出了NFA中哪些状态具有标识为a的转移,对应于NFA状态图中具有标识为a的引出弧的状态集合。在FA理论中,由于需要对确定有限自动机(Deterministic Finite Automata, DFA进行最小化,而使用分割算法对非完全DFA直接进行最小化存在一些问题[12],所以非完全 DFA需要转换为完全DFA[13]
