《NFA如何转换成等价的DFA[共13页]》由会员分享,可在线阅读,更多相关《NFA如何转换成等价的DFA[共13页](13页珍藏版)》请在金锄头文库上搜索。
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. wh
4、ile (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,2,1,3,a,b,a,a,a,a,b,b,b,P72 第3题,NFA转换为等价的DFA,exercise,Thank you!,