非确定的有限状态自动机Non-deterministicFiniteAutomaton-PPT课件

2020/6/4,.,1,非确定的有限状态自动机Non-deterministicFiniteAutomaton,NFA,付国宏黑龙江大学计算机科学技术学院ghfu,第三章有限状态自动机,2020/6/4,.,2,引言,FA的修改DFA对于同一个输入，从同一个状态出发只能有一个转移；能否修改FA，使它对同一个输入从同一个状态出发可以有零个、一个或多个转移；从而得到一个更为紧凑(状态数量较少)、更为容易设计的自动机非确定有穷状态自动机(non-deterministicfiniteautomaton,NFA),2020/6/4,.,3,提要,主要内容NFA非形式化描述、形式定义、NFA与DFA的等价性；-NFA形式定义、-NFA与NFA的等价性重点NFA和-NFA的概念、DFA和NFA以及-NFA和NFA之间的等价转换方法；难点对NFA和-NFA概念的理解；NFA与DFA的等价性证明；,2020/6/4,.,4,提要,主要内容NFA非形式化描述、形式定义、NFA与DFA的等价性；-NFA形式定义、-NFA与NFA的等价性重点NFA和-NFA的概念、DFA和NFA以及-NFA和NFA之间的等价转换方法；难点对NFA和-NFA概念的理解；NFA与DFA的等价性证明；,2020/6/4,.,5,NFA,非形式描述形式定义扩展转移函数从NFA构造DFANFA与DFA的等价性,2020/6/4,.,6,NFA的非形式化描述,NFA对同一个输入符号，从一个状态出发可以有零个、一个或多个转移。,L(M1)=x|x为01结尾的0和1的串,L(M1)=x|x为以0开始、1结尾的0和1的串,2020/6/4,.,7,NFA的非形式化描述(cont.),NFA与DFA的区别并不是对于所有的(q,a)Q,(q,a)都有一个状态与它对应；并不是对于所有的(q,a)Q,(q,a)只对应一个状态；NFA在任意时刻可以处于有穷多个状态；NFA具有“智能”具备同时处理多个状态的能力；具备对输入进行预测的能力；,2020/6/4,.,8,NFA的非形式化描述(cont.),例：M1如何接受00101,q0,q0,q0,q0,q0,q0,q1,q1,q1,q2,q2,不能继续,不能继续,2020/6/4,.,9,NFA的形式定义,非确定的有穷状态自动机(Non-deterministicfiniteautomaton,NFA)五元组：M=(Q,q0,F),有穷状态集,输入字母表,状态转移函数,开始状态q0Q,终止状态集FQ,:Q2Q，(q,a)Q,(q,a)=p1,p2,pm,M在状态q读入字符a，可以选择地将状态变成p1,p2,或pm；,将读头向右移动一个带方格而指向输入字符串的下一个字符；,2020/6/4,.,10,NFA的表示,接受x|x0,1*，且x含有子串00或11的NFA的表示,状态转移表,状态转移图,M=(q0,q1,q2,q3,0,1,q0,q0,q3)(q0,0)=q0,q2,(q0,1)=q0,q2,(q1,0)=q3,(q1,1)=,(q2,0)=,(q2,1)=q3,(q3,0)=q3,(q3,1)=q3,四元组,2020/6/4,.,11,把状态函数扩展到串,设NFAM=(Q,q0,F):Q2Q扩展定义:Q*2Q的递归定义(1)基础：qQ，(q,)=q；(2)归纳：设串x形如wa(w*，a)，qQ,(q,w)=p1,p2,pk，则(q,wa)=p|r(q,w),使得p(r,a)可以不区分(q,a)和(q,a)(q,a)=(q,a),2020/6/4,.,12,把状态函数扩展到串(cont.),设x=a1a2an*，则(q,x)的计算如下：举例：用描述右图所示的NFA处理01100的过程,1.(q0,)=q0,2.(q0,0)=(q0,0)=q0,q1,3.(q0,01)=(q0,1)(q1,1)=q0,q2=q0,q2,4.(q0,011)=(q0,1)(q2,1)=q0,q2q3=q0,q2,q3,5.(q0,0110)=(q0,0)(q2,0)(q3,0)=q0,q1q3=q0,q1,q3,6.(q0,01100)=(q0,0)(q1,0)(q3,0)=q0,q1q3q3=q0,q1,q3,2020/6/4,.,13,NFA接受的语言,NFA接受(识别)的字符串x*，如果(q0,x)F，则称x被M接受；如果(q0,x)F=，则称M不接受x；NFA接受(识别)的语言L(M)=x|x*且(q0,x)F,2020/6/4,.,14,NFA与DFA的比较,DFAvs.NFA,都是正则语言的识别模型；,从定义角度，对于一个输入字符，,NFA可以进入若干个状态；,DFA只能进入一个惟一的状态；,从DFA看待问题的角度来说，,NFA在某一时刻同时进入若干个状态，但是，这若干个状态合在一起的“总效果”相当于它处于一个“综合状态”；,可让DFA用一个状态去对应NFA的一组状态。,DFA可看作是一种特殊的NFA；,2020/6/4,.,15,NFA与DFA的对应关系,NFAMN=(Q,N,q0,FN)与DFAMD=(Q2,D,q0,FD)的对应关系NFA从开始状态q0启动，相应的DFA则从状态q0启动，所以q0=q0；对于NFA的一个状态组q1,q2,qn如果NFA在此状态组时读入字符a后可以进入状态组p1,p2,pm,则让相应的DFA在状态q1,q2,qn读入字符a时，进入状态p1,p2,pm；,DFA能做NFA所做的一切！,为了区分，用表示DFA上的状态集合,2020/6/4,.,16,从NFA构造等价的DFA,设NFAMN=(QN,N,q0,FN)，构造DFAMD=(QD,D,q0,FD)，使得L(MN)=L(MD)方法一：子集构造法MN和MD具有相同的字母表；MD的初始状态是只包含MN初始状态的集合，为区别记作q0；QD是QN的幂集，即；FD是所有至少含有一个MN的接受状态的MN的状态集合的集合，即：FD=S|SFN且SQN；SQN和a，为了计算D，需要检查S中的所有状态p，看看MN在输入a时从p进入那些状态，这些状态的并集即D.,2020/6/4,.,17,从NFA构造等价的DFA(cont.),例3-7构造下图所示的NFA对应的DFA,NFA状态转移图,NFA状态转移表,2020/6/4,.,18,从NFA构造等价的DFA(cont.),针对QN所有子集S和所有输入符号计算D(S,a),2020/6/4,.,19,从NFA构造等价的DFA(cont.),不可达状态(inaccessiblestate),如果存在从q0对应的顶点出发，到达某个状态对应的顶点的路，,则称该状态从开始状态是可达的；,否则，就称该状态从开始状态是不可达的；,2020/6/4,.,20,从NFA构造等价的DFA(cont.),确定可达状态,2020/6/4,.,21,从NFA构造等价的DFA(cont.),绘制DFA状态转移图不可达的状态是无用的或无意义的，可以去掉,q0,q1,q0,q1,q3,1,1,0,0,S,q0,q0,q2,q0,q2,q3,0,1,0,1,1,2020/6/4,.,22,从NFA构造等价的DFA(cont.),小结：子集构造法主要步骤(1)根据给定NFAMN，构造其状态集合的所有子集，即幂集；(2)，计算(3)从q0依次判断S是否可达状态；(4)去掉所有不可达状态，剩下的状态及其相应的转移就构成DFA的状态转移表。,2020/6/4,.,23,从NFA构造等价的DFA(cont.),方法二：画图法先画出开始状态q0的图；如果图中有未处理的顶点任选一个未处理的状态q1,q2,qn；对中的每个字符a，计算(q1,q2,qn,a)；如果(q1,q2,qn，a)已经是图的一个顶点，则在图中画一条从顶点q1,q2,qn到顶点(q1,q2,qn，a)标记为a的弧；如果(q1,q2,qn，a)不是图的一个顶点，则在图中增加一个标记为(q1,q2,qn，a)的顶点，并画一条从顶点q1,q2,qn到顶点(q1,q2,qn，a)标记为a的弧；如此重复下去，直到图中不存在未处理的顶点。,2020/6/4,.,24,从NFA构造等价的DFA(cont.),q0,q1,1,0,S,q0,q0,q2,(3)考察状态q0,q1关于0和1的转移,q0,q1,q3,0,1,(4)考察状态q0,q2关于0和1的转移,0,1,q0,q2,q3,(5)考察状态q0,q1,q3关于0和1的转移,1,(6)考察状态q0,q2,q3关于0和1的转移,0,例：用绘图法构造例3-7所示的NFA对应的DFA,(2)考察状态q0关于0和1的转移,(1)先画出开始状态q0,2020/6/4,.,25,NFA与DFA等价,定理3-1NFA与DFA等价证明(1)构造与NFAM1等价的DFAM2设M1=(Q1,1,q0,F1)，构造M2=(Q2,2,q0,F2)Q2=2QF2=p1,p2,pm|p1,p2,pmQ1且p1,p2,pmF12(q1,q2,qn,a)=p1,p2,pm1(q1,q2,qn,a)=p1,p2,pm,2020/6/4,.,26,NFA与DFA等价(cont.),(2)x*，施归纳于|x|证明：1(q0,x)=p1,p2,pm2(q0,x)=p1,p2,pm当|x|=0时，x=1(q0,)=q0,2(q0,)=q0,结论成立；设当|x|=n时结论成立，往证当|x|=n+1时结论也成立不妨设x=wa，|w|=n，a1(q0,wa)=1(1(q0,w),a)=1(q1,q2,qn,a)=p1,p2,pm由归纳假设1(q0,w)=q1,q2,qn2(q0,w)=q1,q2,qn,2020/6/4,.,27,NFA与DFA等价(cont.),根据2的定义2(q1,q2,qn,a)=p1,p2,pm1(q1,q2,qn,a)=p1,p2,pm；于是，2(q0,wa)=2(2(q0,w),a)=2(q1,q2,qn,a)=p1,p2,pm；因此，如果1(q0,wa)=p1,p2,pm则必有2(q0,wa)=p1,p2,pm；由上述推导可知，反向的推导也成立；因此结论对|x|=n+1也成立；由归纳法原理，结论对x*成立。,2020/6/4,.,28,NFA与DFA等价(cont.),(3)证明L(M1)=L(M2)设xL(M1)，且1(q0,x)=p1,p2,pm，则1(q0,x)F1；即p1,p2,pmF1；由F2的定义，p1,p2,pmF2；再由结论(2)知2(q0,x)=p1,p2,pm；于是，xL(M2)；故L(M1)L(M2)；反过来推，可得L(M2)L(M1)；综合(1)、(2)和(3)，定理成立。,2020/6/4,.,29,-NFA,非形式描述形式定义闭包扩展转移函数NFA与DFA的等价性,2020/6/4,.,30,-NFA的非形式描述,构造接受语言0n1m2k|n，m，k1的NFAM1,S,0,1,2,构造接受语言0n1m2k|n，m，k0的NFAM2,显然，构造M2比构造M1复杂很多,2020/6/4,.,31,-NFA的非形式描述(续),接受语言0n1m2k|n，m，k0的NFA能否构造成下图所示的M3,S,0,1,2,M3在某一状态下可以不移动读头(即读入字符)，而知改变状态；,M3的构造显然比M2更容易；,希望M3和M2是等价的,2020/6/4,.,32,-NFA的形式定义,带空移动的非确定有穷状态自动机Non-deterministicfiniteautomatonwith-moves,-NFA五元组：M=(Q,q0,F),有穷状态集,输入字母表,状态转移函数,开始状态q0Q,终止状态集FQ,:Q()2Q，,(q,a)Q,(q,a)=p1,p2,pm：M在状态q读入字符a，可以选择地将状态变成p1,p2,或pm，并将将读头向右移格而指向输入字符串的下一个字符；,qQ，(q,)=p1,p2,pm：表示M在状态q不读入任何字符，即M在状态q做一个空移动(又称为移动)，并选择地将状态变成p1,p2,或pm；,2020/6/4,.,33,-NFA的表示,接受语言0n1m2k|n，m，k0的-NFA的表示,状态转移表,状态转移图,M=(q0,q1,q2,0,1,2,q0,q3)(q0,)=q1,(q0,0)=q0,(q0,1)=,(q0,2)=,(q1,)=q2,(q1,0)=,(q1,1)=q1,(q1,2)=,(q2,)=,(q2,0)=,(q2,1)=,(q2,2)=q2,四元组,2020/6/4,.,34,-闭包(-CLOSURE),设-NFAM=(Q,q0,F)，qQ,q的-闭包，定义为从q经所有的路径可以到达的状态(包括q自身)-CLOSURE(q)=p|从q到p有一条标记为的路PQ，例子,-CLOSE(q1)=q1,q2,q4,q5,q6,q7,-CLOSE(q2)=q2,q4,q5,q6,q7,-CLOSE(q7)=q5,q7,-CLOSE(q2,q7)=-CLOSE(q2)-CLOSE(q7)=q2,q4,q5,q6,q7,2020/6/4,.,35,扩展状态转移函数,扩展状态转移函数到输入串设NFAM=(Q,q0,F):Q2Q扩展定义：:Q*2Q的递归定义(1)基础：qQ，(q,)=-CLOSURE(q)；(2)归纳：设串x=wa(w*，a)，qQ,假设(q,w)=p1,p2,pk，且则,2020/6/4,.,36,扩展状态转移函数(cont.),扩展状态转移函数到子集设NFAM=(Q,q0,F):Q2Q进一步扩展：2Q2Q(P,a)2Q进一步扩展:2Q*2Q(P,x)2Q*,2020/6/4,.,37,扩展状态转移函数(cont.),注意：在-NFA中，对任意a，qQ，(q,a)(q,a)(q,a)包含所有可从q出发、沿着标记为a的路径(包括标记为的弧)所能到达的各个状态；(q,a)仅包含所有可从q出发、沿着标记为a的弧线所能到达的那些状态；类似地(q,)(q,),在-NFA中，必须区分和！,2020/6/4,.,38,扩展状态转移函数(cont.),例：vs.,2020/6/4,.,39,扩展状态转移函数(cont.),例：根据下图所示的-NFA计算(q0,01)(1)计算(q0,)(q0,)=-CLOSURE(q0)=q0,q1,q2(2)计算(q0,0)(q0,0)=-CLOSURE(q0,),0)=-CLOSURE(q0,q1,q2,0)=-CLOSURE(q0,0)(q1,0)(q2,0)=-CLOSURE(q0)=-CLOSURE(q0)=q0,q1,q2(3)计算(q0,01)(q0,01)=-CLOSURE(q0,0),1)=-CLOSURE(q0,q1,q2,1)=-CLOSURE(q0,1)(q1,1)(q2,1)=-CLOSURE(q1)=-CLOSURE(q1)=q1,q2,2020/6/4,.,40,-NFA接受的语言,x*，,如果(q0,x)F，则称x被M接受；,于是，-NFAM接受或识别的语言L(M),设-NFAM=(Q,q0,F)，,如果(q0,x)F=，则称x不被M接受；,2020/6/4,.,41,从-NFA构造等价的NFA,给定-NFAM1=(Q,1,q0,F1)，构造NFAM2=(Q,2,q0,F2)，使得L(M2)=L(M1)M2和M1具有相同的字母表、相同的状态集和相同的初始状态；接受状态F2状态转移函数2(q,a)Q，2(q,a)=1(q,a),2020/6/4,.,42,从-NFA构造NFA(cont.),例：设有下表所示的-NFAM1=(Q,1,q0,F1)，构造相应的NFAM2确定F2因为-CLOSURE(q0)=q0,q1,q2F1则F2=F1q0=q0,q2通过计算1(q,a)，确定2=1(q,a)即可得到NFAM2=(Q,2,q0,F2),2020/6/4,.,4