编译原理3.3.3-2NFA的确定化

第三章词法分析3.1对于词法分析器的要求3.2词法分析器的设计3.3正规表达式和自动机3.4词法分析器的自动产生3.3.3非确定有限自动机1.NFA的定义2.NFA的表示方式3.NFA如何作为识别机制4.一个NFA所定义的语言L(M)5.有穷自动机等价的定义6.NFA的确定化6.NFA的确定化DFA和NFA的区别•初态是否唯一•转换函数是否为单值映射•DFA是NFA的特例定理•设L为一个由NFA接受的集合，则存在一个接受L的DFA。•对于每个NFAM存在一个DFAM′,使L(M)=L(M′)。p49NFA的确定化–子集法定义对状态集合I的几个有关运算1)状态集合I的ε-闭包2)状态集合I的a弧转换1).状态集合I的ε-闭包ε-closure(I)(a)若q∈I,则q∈ε_CLOSURE(I)；(b)若q∈I,则从q出发经任意条ε弧而能到达的任何状态q′都属于ε_CLOSURE(I)；补充例:I＝{1},ε-closure(I)={1,2}I＝{5},ε-closure(I)={5,6,2}I＝{1,5},ε-closure(I)={1,2,5,6}补充例ε-closure({0})={0,1,2,4,7}ε-closure({3，8})={3,6,1,2,4,7,8}2).状态集合I的a弧转换IaI＝{s1,s2,…,sj}move(I,a)=δ(s1,a)δ(s2,a)…δ(sj,a)Ia=ε_CLOSURE(move(I,a))补充例:I={1，2}Ia=ε-closure(move(I,a))=ε-closure(δ(1,a)δ(2,a))=ε-closure({5,4,3})={5,4,3,6,2,7,8}12543状态集合I的a弧转换Ia•Ia子集是从子集I出发，经过一条a弧（前后可以跳过任意条弧）而到达的状态的集合。NFA的确定化算法•步骤一:假定NFAN={S,∑,δ,S0,F},对N的状态转换图进行改造得到N′•步骤二:将NFAN′确定化为DFAM(子集法)步骤一:假定NFAN={S,∑,δ,S0,F},对N的状态转换图进行以下改造①引入新的初态结点X和终态结点Y从X到S0中任意状态结点连一条ε箭弧,从F中任意状态结点连一条ε箭弧到Y.将NFA转换成具有唯一初态和唯一终态的NFA②对N的状态转换图施行替换得到N′使状态转换图中的每条箭弧上的标记或为ε,或为∑中的单个字母.步骤二:将NFAN′确定化为DFAMNFAN′={S,∑,δ,S0,F},构造一个DFAM=(SM,∑M,δM,S0M,FM)，使得L(M)=L(N′)(1)M的状态集SM由S的一些子集组成用[S1S2...Sj]表示SM的元素，其中S1,S2,,...Sj是S的状态。(SM是一个子集族)(2)M的输入字母表∑M和N′是相同的，即∑M＝∑(3)转换函数δMδM([S1S2...Sj],a)=ε-closure(move([S1,S2,...Sj],a))即集合[S1S2...Sj]的a弧转换(4)M的初态S0M=ε-closure(S0),从N的初态S0出发,经过任意条ε弧所能到达的状态所组成的集合(5)M的终态集合FMFM={[SjSk...Se]，其中[SjSk...Se]∈SM且{Sj,Sk,,...Se}∩F≠φ}，即构造的子集族中凡是含有原NFA终态的子集都是DFA的终态。•S0M=ε-closure(S0)•对每个a∑,将S0M的a弧转换作为下一状态置于SM中。即:把从S0出发经过一条标记为a的弧所能到达的状态(其前其后可经过若干条ε矢线)所组成的集合作为下一个状态置于SM中.•如此反复,直到没有新的状态出现为止.将NFAN′确定化为DFAM的步骤:补充例:NFA的确定化–子集法解题过程见黑板上例确定化结果约定:NFA若以状态转换图（矩阵）给出，确定化后的DFA也以状态转换图（矩阵）给出。*补充:子集法的算法假定所构造的子集族为C，C=(T1,T2,...Ti),T1,...Ti为状态S的子集。①令e-closure(X)为C中唯一成员，且它是未被标记的②while(C中存在尚未被标记的子集T)do{标记T；for每个输入字母ado{U:=Ta；ifU不在C中then将U作为未标记的子集加在C中}}