NFA转化为DFA的转换算法及实现

摘要

确定有限⾃动机确定的含义是在某种状态，⾯临⼀个特定的符号只有⼀个转换，进⼊唯⼀的⼀个状态。不确定的有限⾃动机则相反，在某种状态下，⾯临⼀个特定的符号是存在不⽌⼀个转换，即是可以允许进⼊⼀个状态集合。

在⾮确定的有限⾃动机NFA中,由于某些状态的转移需从若⼲个可能的后续状态中进⾏选择，故⼀个NFA对符号串的识别就必然是⼀个试探的过程。这种不确定性给识别过程带来的反复，⽆疑会影响到FA的⼯作效率。⽽DFA则是确定的,将NFA转化为DFA将⼤⼤提⾼⼯作效率,因此将NFA转化为DFA是有其⼀定必要的。

对于任意的⼀个不确定有限⾃动机（NFA）都会存在⼀个等价的确定的有限⾃动机（DFA），即L(N)=L(M)。本⽂主要是介绍如何将NFA转换为与之等价的简化的DFA，通过具体实例，结合图形，详细说明转换的算法原理。关键词：有限⾃动机；确定有限⾃动机（DFA），不确定有限⾃动机（NFA）Abstract

Finite automata is determinate and indeterminate two class. Determine the meaning is in a certain state, faces a particularsymbol only one conversion, enter only one state. Not deterministic finite automata is the opposite, in a certain state, faces aparticular symbol is the presence of more than one conversion, that is to be allowed to enter a state set.

Non deterministic finite state automata NFA, because of some state are transferred from a number of possible follow-up stateare chosen, so a NFA symbol string recognition must be a trial process. This uncertainty to the recognition process broughtabout by repeated, will undoubtedly affect the efficiency of the FA. While the DFA is determined, converting NFA to DFA willgreatly improve the working efficiency, thus converting NFA to DFA is its necessary.

For any a nondeterministic finite automaton ( NFA ) can be an equivalent deterministic finite automaton ( DFA ), L ( N ) =L ( M). This paper mainly introduces how to convert NFA to equivalent simplified DFA, through concrete examples, combined withgraphics, a detailed description of the algorithm principle of conversion.

Keywords:：finite automata; deterministic finite automaton ( DFA ), nondeterministic finite automaton ( NFA⽬录1.前⾔： (1)1.1背景 (1)1.2实践⽬的 (1)1.2课程实践的意义 (1)2.NFA和DFA的概念 (2)2.1 不确定有限⾃动机NFA (2)2.2确定有限⾃动机DFA (3)

3．从NDF到DFA的等价变化步骤 (5)3.1转换思路 (5)3.2.消除空转移 (5)3.3⼦集构造法 (7)4程序实现 (9)4.1程序框架图 (9)4.2 数据流程图 (9)4.3实现代码 (10)4.4运⾏环境 (10)

4.5程序实现结果 (10)5.⽤户⼿册 (12)6.课程总结： (12)7.参考⽂献 (12)8. 附录 (13)1.前⾔：1.1背景

有限⾃动机作为⼀种识别装置，它能准确地识别正规集，即识别正规⽂法所定义的语⾔和正规式所表⽰的集合，引⼊有穷⾃动机这个理论，正是为词法分析程序的⾃动构造寻找特殊的⽅法和⼯具。

有限⾃动机（Finite Automate）是⽤来模拟实物系统的数学模型，它包括如下五个部分：有穷状态集States输⼊字符集Input symbols转移函数Transitions起始状态Start state接受状态Accepting state(s)1.2实践⽬的

（1）设计、编制、调式⼀个有穷⾃动机程序，加深对NFA转换为DFA的原理的理解。（2）掌握NFA确定化的过程。1.2课程实践的意义

通过本课程设计教学所可以使我们充分理解和掌握NFA，DFA以及NFA确定化过程的相关概念和知识，理解和掌握⼦集法的相关知识和应⽤，编程实现对输⼊NFA转换成DFA输出的功能。2.NFA和DFA的概念2.1 不确定有限⾃动机NFA

NFA(nondeterministic finite-state automata)即⾮确定有限⾃动机, ⼀个⾮确定的有限⾃动机NFA M’是⼀个五元式:NFA M’=(S, Σ∪{ε}, δ, S0, F)

其中 S—有限状态集，Σ∪{ε}—输⼊符号加上ε,即⾃动机的每个结点所射出的弧可以是Σ中⼀个字符或是ε.S0—初态集 F—终态集δ—转换函数 S×Σ∪{ε} →2S

(2S --S的幂集—S的⼦集构成的集合）例1：NFA M=({S,P,Z},{0,1},f,{s,p},{z})其中

f(s,0)={p} f(z,0)={p} f(p,1)={z}f(z,1)={p} f(s,1)={s,z}①NFA的状态图表⽰如下：

②NFA矩阵表⽰：

2.2确定有限⾃动机DFA

DFA(deterministic finite-state automata)即确定有限⾃动机，⼀个确定的有限⾃动机DFA M是⼀个五元式:M=(S, Σ，δ, S0, Z)其中:

S —有限状态集Σ—输⼊字母表

δ—映射函数(也称状态转换函数)S×Σ→S

δ(s,a)=S ’ , S, S ’ ∈S, a ∈Σ S0 —初始状态 S0 ∈S Z —终⽌状态集 Z S

例2：DFA M=({S,U,V,Q},{a,b},f,s,{Q}) 其中f 的定义为： f(S,a)=U f(S,b)=V f(U,a)=Q f(U,b)=V f(V,a)=U f(V,b)=Q f(Q,a)=Qf(Q,b)=Q ① DFA 的状态图表⽰：

假如DFA M 含有m 个状态，n 个输⼊符，那么这个状态含有m 个节点，每个节点最多有n 个弧射出，整个图整个图含有唯⼀⼀个初态结点和若⼲个终态结点，初态结点冠以双箭头“=>”或标以“-”，终态结点⽤双圈表⽰或标以“+”，若 f(ki ,a)=kj ，则从状态结点ki 到状结点kj 画标记为a 的弧：

② DFA 矩阵表⽰：

⼀个DFA 还可以⽤⼀个矩阵表⽰，该矩阵的⾏表⽰状态，列表⽰输⼊字符，矩阵元素表⽰相应状态⾏和输⼊字符列下的新状态，即k ⾏a 列为f(k,a)的值。⽤双箭头=>标明初态；否则第⼀⾏即是初态，相应终态⾏在表的右端标以1，⾮终态标以0.

3．从NDF到DFA的等价变化步骤

事实已经证明了不管是⾮确定的有限⾃动机M还是具有ε-转移的⾮确定的有限⾃动机，都可以找到⼀个与之等价的确定有限⾃动机，使得L（M）=L（M’）。3.1转换思路

由⾮确定的有限⾃动机出发构造与之等价的确定的有限⾃动机的办法是确定的有限⾃动机的状态对应于⾮确定的有限⾃动机的状态集合，即要使转换后的DFA的每⼀个状态对应NFA的⼀组状态。该DFA使⽤它的状态去记录在NFA读⼊⼀个输⼊符号后可能到达的所有状态，也就是说，在读⼊符号串a1a2a3…an之后，该DFA处在这样⼀个状态，该状态表⽰这个NFA的状态的⼀个⼦集T，⽽T 是从NFA的开始状态沿着某个标记为a1a2a3…an的路径可以到达的那些状态。3.2.消除空转移

形式的产⽣式，即消除空转移。状态集合I的a弧转换Ia:定义.消除N

为⼀状态集，是指从状态集I出发先经过a弧后再经过若⼲条ε弧⽽能到达的状态的集合。可以写作： Ia= ε-closure(J)，J=move(I,a),其中，J是从I中任⼀状态出发经过⼀条a弧到达的状态集合，记为move(I,a)。s 表⽰NFA的状态，T 表⽰NFA的状态集合，a表⽰⼀个input symbolε-transition(ε转换)就是说input symbol为ε时的transition(转换)

例如：

对于以下状态图中：ε-closure({0})={0,1,2,4,7}

在这⾥设I={0,1,2,4,7}，则因为有move(I,a)={3,8}=J,所以Ia= ε-closure(J)= ε-closure({3,8})={1,2,3,4,6,7,8}

ε

3.3⼦集构造法

确定化每个多重转移，即拆分多值函数为单位函数,具体转换，采⽤⼦集构造法。以下⾯的基于字母表Σ={a,b}上的具有ε-转移的⾮确定有限⾃动机M为例。

步骤1：以I，Ia、Ib等为列做表，其中I列第⼀⾏的内容是初态的ε- 闭包所

得到的状态集合。并以此为I计算Ia、Ib等，⽽且在所计算出的Ia、Ib等中若有新的状态集产⽣，就重复以此新的集合为I再此计算Ia、Ib等，直到在所得的Ia、Ib等中不再产⽣新的状态集为⽌。

步骤2：在上表中将原NFA初态的ε-闭包作为转换后的DFA的初态，包含原NFA 终态的状态作为转换后的DFA的终态，并进⾏重新编号得到转换后的DFA的状态转移矩阵如下：

步骤3：画出转换后的DFA的状态图：