NFA如何转换成等价的DFA

1、主讲：陈小娟主讲：陈小娟西南大学荣昌校区信息管理系西南大学荣昌校区信息管理系 NFA NFA转换为等价的转换为等价的DFADFA4.34.3编译原理编译原理4.3.1 4.3.1 基本概念基本概念 (1) (1) FAFA（ finite automatafinite automata）有穷自动机）有穷自动机 作为一种作为一种识别装置识别装置，它能准确地，它能准确地识别识别文法所文法所定义的定义的语言语言和正规式表示的和正规式表示的集合集合。 引入引入FAFA的目的：是为词法分析程序的自动构的目的：是为词法分析程序的自动构造寻找方法和工具。造寻找方法和工具。 NFADFAFA(2) DFA(d

2、eterministic finite automata)(2) DFA(deterministic finite automata) 确定的确定的有穷自动机有穷自动机(3) NFA(3) NFA（nondeterministic finite automatanondeterministic finite automata） 不确定的不确定的有穷自动机有穷自动机 两者的区别是：转换函数和初态方面的不同两者的区别是：转换函数和初态方面的不同4.3.1 4.3.1 基本概念基本概念(1)(1)定理定理: :设设L L为一个由不确定的有穷自动机接受的集合，为一个由不确定的有穷自动机接受的集合， 则

3、存在一个接受则存在一个接受L L的确定的有穷自动机。的确定的有穷自动机。(2)(2)子集法：子集法：将不确定的有穷自动机转换成接受同样语将不确定的有穷自动机转换成接受同样语 言的确定的有穷自动机。言的确定的有穷自动机。4.3.2 NFA4.3.2 NFA转换为等价的转换为等价的DFADFA的算法的算法定义对状态集合定义对状态集合I I的几个有关运算：的几个有关运算：1 1 状态集合状态集合I I的的 - -闭包，表示为闭包，表示为，定义为一状态集，是状态，定义为一状态集，是状态集集I I中的任何状态中的任何状态S S经任意条经任意条 弧而能到达的状态的集合。弧而能到达的状态的集合。 I=1,

4、-closure(I)= 1,2； 12534aa a例例687I=5, -closure(I)= 5,6,2；4.3.2 NFA4.3.2 NFA转换为等价的转换为等价的DFADFA的算法的算法2 状态集合状态集合I的的a弧转换，表示为弧转换，表示为定义为状态集合定义为状态集合J，其中，其中J是是所有那些可从所有那些可从I的某一状态经过一条的某一状态经过一条a弧而到达的状态的全体。弧而到达的状态的全体。 定义定义Ia = -closure(J)move(1,2,a)= 5,3,4 -closure(5,3,4)=Ia =2,3,4,5,6,7,812534aa a例例6874.3.2 NFA

5、4.3.2 NFA转换为等价的转换为等价的DFADFA的算法的算法构造构造NFA NNFA N的状态的状态K K的子集的算法的子集的算法算法描述如下：算法描述如下：假定所构造的假定所构造的子集族子集族为为C，即，即C= (T1, T2,. TI),其中其中T1, T2,. TI为状态为状态K的子集。的子集。1. 开始，令开始，令 -closure(K0)为为C中中唯一唯一成员，成员， 并且它是并且它是未被标记未被标记的。的。构造构造NFA NNFA N的状态的状态K K的子集的算法：的子集的算法：2.2.while while （C C中存在尚未被标记的子集中存在尚未被标记的子集T T）dod

6、o 标记标记T T； for for 每个输入字母每个输入字母a doa do U:= U:= -closure(move(T,a)-closure(move(T,a)； if Uif U不在不在C C中中 then then 将将U U作为未标记的子集加在作为未标记的子集加在C C中中 例例 将下图的将下图的NFA NNFA N转换成转换成DFA MDFA M023456789101bbbaaNFA N 图图4.3.3 应用举例应用举例023456789101bbbaaIaIbT0= -closure(0) =0,1,2,4,71,2,3,4,6,7,81,2,4,5,6,7 T1= 1,2,3,4,6,7,81,2,3,4,6,7,8 1,2,4,5,6,7,9 T2= 1,2,4,5,6,71,2,3,4,6,7,8 1,2,4,5,6,7 T3= 1,2,4,5,6,7,9 T4= 1,2,4,5,7,10 1,2,3,4,6,7,8 1,2,4,5,7,10 1,2,3,4