NFA如何转换成等价的DFA

主讲：陈小娟西南大学荣昌校区信息管理系NFA转换为等价的DFA4.3编译原理4.3.1基本概念(1)FA（finiteautomata）有穷自动机作为一种识别装置，它能准确地识别文法所定义的语言和正规式表示的集合。引入FA的目的：是为词法分析程序的自动构造寻找方法和工具。NFADFAFA(2)DFA(deterministicfiniteautomata)确定的有穷自动机(3)NFA（nondeterministicfiniteautomata）不确定的有穷自动机两者的区别是：转换函数和初态方面的不同4.3.1基本概念(1)定理:设L为一个由不确定的有穷自动机接受的集合，则存在一个接受L的确定的有穷自动机。(2)子集法：将不确定的有穷自动机转换成接受同样语言的确定的有穷自动机。4.3.2NFA转换为等价的DFA的算法定义对状态集合I的几个有关运算：1状态集合I的-闭包，表示为-closure(I)，定义为一状态集，是状态集I中的任何状态S经任意条弧而能到达的状态的集合。I={1},-closure(I)={1,2}；12534aaa例687I={5},-closure(I)={5,6,2}；4.3.2NFA转换为等价的DFA的算法2状态集合I的a弧转换，表示为move(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,8}12534aaa例6874.3.2NFA转换为等价的DFA的算法构造NFAN的状态K的子集的算法算法描述如下：假定所构造的子集族为C，即C=(T1,T2,...TI),其中T1,T2,...TI为状态K的子集。1.开始，令-closure(K0)为C中唯一成员，并且它是未被标记的。构造NFAN的状态K的子集的算法：2.while（C中存在尚未被标记的子集T）do{标记T；for每个输入字母ado{U:=-closure(move(T,a))；ifU不在C中then将U作为未标记的子集加在C中}}例将下图的NFAN转换成DFAM023456789101εεεεεεεεbbbaaNFAN图4.3.3应用举例023456789101εεεεεεεεbbbaaIaIbT0=-closure(0)={0,1,2,4,7}{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}IaIb012113212314412b02134abaaaabbbP72第3题NFA转换为等价的DFAexercise