NFA如何转换成等价的DFA.ppt

1、主讲：陈小娟 西南大学荣昌校区信息管理系,NFA转换为等价的DFA,4.3,编译原理,4.3.1 基本概念,(1) FA（ finite automata）有穷自动机 作为一种识别装置，它能准确地识别文法所定义的语言和正规式表示的集合。 引入FA的目的：是为词法分析程序的自动构造寻找方法和工具。,NFA,DFA,FA,(2) DFA(deterministic finite automata) 确定的有穷自动机 (3) NFA（nondeterministic finite automata） 不确定的有穷自动机 两者的区别是：转换函数和初态方面的不同,4.3.1 基本概念,(1)定理:设L为

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

3、态集合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,8,1,2,5,3,4,a,a,a,例,6,8,7,4.3.2 NFA转换为等价的DFA的算法,构造NFA N的状态K的子集的算法,算法描述如下： 假定所构造的子集族为C，即C= (T1, T2,. TI), 其中T1, T2,. TI为状态K的子集。 1. 开始，令-closure(K0)为C中唯一成员， 并且它是未被标记的。,构造NFA N的状态K的子集的算法：,2.whi

4、le （C中存在尚未被标记的子集T）do 标记T； for 每个输入字母a do U:= -closure(move(T,a)； if U不在C中 then 将U作为未标记的子集加在C中 ,例 将下图的NFA N转换成DFA M,NFA N 图,4.3.3 应用举例,0,2,3,4,5,6,7,8,9,10,1,b,b,b,a,a,1,2,3,4,6,7,8,1,2,4,5,6,7,T1= 1,2,3,4,6,7,8,1,2,3,4,6,7,8,1,2,4,5,6,7,9,T2= 1,2,4,5,6,7,1,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,6,7,8,1,2,4,5,6,7,b,0