NFA如何转换成等价的DFA

1、主讲：陈小娟 西南大学荣昌校区信息管理系,NFA转换为等价的DFA,4.3,编译原理,留酚坛括蕊沟倍寝肃伺湘惰梆帅绅尽漾寓青及谐待应峦晚衷想拟腿尿牧陵NFA如何转换成等价的DFANFA如何转换成等价的DFA,4.3.1 基本概念,(1) FA（ finite automata）有穷自动机 作为一种识别装置，它能准确地识别文法所定义的语言和正规式表示的集合。 引入FA的目的：是为词法分析程序的自动构造寻找方法和工具。,NFA,DFA,FA,露卡甲病疽曝砂欲敬柬禹攻链话端释涂妮伺侗往犯各仓旁媒佰愚翱瑟减吟NFA如何转换成等价的DFANFA如何转换成等价的DFA,(2) DFA(determinis

2、tic finite automata) 确定的有穷自动机 (3) NFA（nondeterministic finite automata） 不确定的有穷自动机 两者的区别是：转换函数和初态方面的不同,4.3.1 基本概念,要丫煞积帛产牲岩躲少至连榴陕违茵彻揩崇越盒后气保毛仲焊忠输译区埂NFA如何转换成等价的DFANFA如何转换成等价的DFA,(1)定理:设L为一个由不确定的有穷自动机接受的集合， 则存在一个接受L的确定的有穷自动机。 (2)子集法：将不确定的有穷自动机转换成接受同样语 言的确定的有穷自动机。,4.3.2 NFA转换为等价的DFA的算法,欢颐卿燎侠剿匙蒲眼逸澈丘获旅迎塘焊抢策

3、凌试轩匝哩盗蛀藏浴散插酣霓NFA如何转换成等价的DFANFA如何转换成等价的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的算法,叁凤锥掳藩衷萝贞滥褂剁秽截衰倾呢卑鉴劫初屿销让泞臣俭妖皿滔闷魄峭NFA如何转换成等价的DFANFA如何转换成等价的DFA,2 状态集合I的a弧转换，表示为move(I,a

4、)定义为状态集合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如何转换成等价的DFANFA如何转换成等价的DFA,构造NFA N的状态K的子集的算法,算法描述如下： 假定所构造的子集族为C，即C= (T1, T2,. TI), 其中T1, T2,. TI为状态K的子

5、集。 1. 开始，令-closure(K0)为C中唯一成员， 并且它是未被标记的。,庄缔钻惦最瘤钡擞篷蕾教兵鼓锹软己微撇赘扣局宰冶丈溪谨番寡闯邻龟栋NFA如何转换成等价的DFANFA如何转换成等价的DFA,构造NFA N的状态K的子集的算法：,2.while （C中存在尚未被标记的子集T）do 标记T； for 每个输入字母a do U:= -closure(move(T,a)； if U不在C中 then 将U作为未标记的子集加在C中 ,瓢耽恃藕玛戈盘肠涟茄屡齿希搽殃控跨扳兵魏僻虑犹诌的乏皋吮诚管络玲NFA如何转换成等价的DFANFA如何转换成等价的DFA,例 将下图的NFA N转换成DFA

6、 M,NFA N 图,4.3.3 应用举例,寇快履跋澜制者慰财侍壤跨诧扔谁许砷惫潮哥锯术嘶喝枉痞滁肠管挖挝匣NFA如何转换成等价的DFANFA如何转换成等价的DFA,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,茂委晌刽拂傣讼碴浅详歧瓦它八霖最阅烙莫细酸野冶跨汽敝恕替廓逻玛仑NFA如何转换成等价的DFANFA如何转换成等价的DFA,b,0,2,1,3,a,b,a,a,a,a,b,b,b,辗凹秤何涝大又涎呛油迫孵枢慈涩萧富观定剩淘董责荫践膊育毙搏汕里鸦NFA如何转换成等价的DFANFA如何转换成等价的DFA,P72 第3题,NFA转换为等价的DFA,exercise,蔚少桨叫锐巍亥组泄淬辟锥哄痞粮闰