形式语言与自动机理论电子教案-03省名师优质课赛课获奖课件市赛课百校联赛优质课一等奖课件.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,本资料仅供参考，不能作为科学依据。谢谢。本资料仅供参考，不能作为科学依据。本资料仅供参考，不能作为科学依据。谢谢。本资料仅供参考，不能作为科学依据。,第3章 有穷状态自动机,主要内容,确定有穷状态自动机(DFA),作为对实际问题抽象、直观物理模型、形式定义，DFA接收句子、语言，状态转移图。,不确定有穷状态自动机(NFA),定义；,NFA与DFA等价性；,1/146,7/1/2025,1,第3章 有穷状态自动机,带空移动有穷状态自动机(-NFA),定义。,-NFA与DFA等价性。,FA是正则语言识别器,正则文法(RG)与FA等价性。,相互转换方法。,带输出有穷状态自动机。,双向有穷状态自动机。,2/146,7/1/2025,2,第3章 有穷状态自动机,重点：DFA概念，DFA、NFA、-NFA、RG之间等价转换思绪与方法。,难点：对DFA概念了解，DFA、RG结构方法，RG与FA等价性证实。,3/146,7/1/2025,3,3.1 语言识别,推导和归约中回溯问题将对系统效率产生极大影响,S,aA|aB,A,aA|c,B,aB|d,分析句子,aaac,过程中可能需要回溯。,4/146,7/1/2025,4,3.1 语言识别,系统识别语言a,n,c|n1a,n,d|n1字符串过程中状态改变图示以下：,5/146,7/1/2025,5,3.1 语言识别,识别系统(模型),系统含有有穷个状态，不一样状态代表不一样意义。按照实际需要，系统能够在不一样状态下完成要求任务。,我们能够将输入字符串中出现字符聚集在一起组成一个字母表。系统处理全部字符串都是这个字母表上字符串。,6/146,7/1/2025,6,3.1 语言识别,系统在任何一个状态(当前状态)下，从输入字符串中读入一个字符，依据当前状态和读入这个字符转到新状态。当前状态和新状态能够是同一个状态，也能够是不一样状态；当系统从输入字符串中读入一个字符后，它下一次再读时，会读入下一个字符。这就是说，相当于系统维持有一个读写指针，该指针在系统读入一个字符后指向输入串下一个字符。,7/146,7/1/2025,7,3.1 语言识别,系统中有一个状态，它是系统开始状态，系统在这个状态下开始进行某个给定句子处理。,系统中还有一些状态表示它到当前为止所读入字符组成字符串是语言一个句子，把全部将系统从开始状态引导到这种状态字符串放在一起组成一个语言，该语言就是系统所能识别语言。,8/146,7/1/2025,8,3.1 语言识别,对应物理模型,一个右端无穷输入带。,一个有穷状态控制器,(finite state control,FSC),。,一个读头。,系统每一个动作由三个节拍组成：读入读头正注视字符；依据当前状态和读入字符改变有穷控制器状态；将读头向右移动一格。,9/146,7/1/2025,9,3.1 语言识别,有穷状态自动机物理模型,10/146,7/1/2025,10,3.2有穷状态自动机,有穷状态自动机(finite automaton,FA),M=(Q，q,0,，F),Q状态非空有穷集合。,qQ，q称为M一个,状态(state),。,输入字母表(Input alphabet),。输入字符串都是上字符串。,q,0,q,0,Q，是M,开始状态(initial state),，也可叫做初始状态或者开启状态。,11/146,7/1/2025,11,3.2有穷状态自动机,状态,转移函数(transition function),，有时候又叫做状态转换函数或者移动函数。：Q,Q，对,(q，a)Q，(q，a)=p表示：M在状态q读入字符a，将状态变成p，并将读头向右移动一个带方格而指向输入字符串下一个字符。,FF,Q，是M,终止状态(final state),集合。,qF，q称为M,终止状态，,又称为,接收状态(accept state)。,12/146,7/1/2025,12,3.2有穷状态自动机,例 3-1,下面是一个有穷状态自动机,M,1,=(q,0,，q,1,，q,2,，0，,1,，q,0,，q,2,),其中，,1,(q,0,0)=q,1,，,1,(q,1,0)=q,2,，,1,(q,2,0)=q,1,用表3-1表示,1,。,状态说明,状态,输入字符,0,开始状态,q,0,q,1,q,1,q,2,终止状态,q,2,q,1,13/146,7/1/2025,13,3.2有穷状态自动机,M,2,=(q,0,，,q,1,，,q,2,，,q,3,，,0,，,1,，,2,，,2,，,q,0,，,q,2,),2,(q,0,0)=q,1,，,2,(q,1,0)=q,2,2,(q,2,0)=q,1,，,2,(q,3,0)=q,3,2,(q,0,1)=q,3,，,2,(q,1,1)=q,3,2,(q,2,1)=q,3,，,2,(q,3,1)=q,3,2,(q,0,2)=q,3,，,2,(q,1,2)=q,3,2,(q,2,2)=q,3,，,2,(q,3,2)=q,3,14/146,7/1/2025,14,3.2有穷状态自动机,状态说明,状态,输入字符,0,1,2,开始状态,q,0,q,1,q,3,q,3,q,1,q,2,q,3,q,3,终止状态,q,2,q,1,q,3,q,3,q,3,q,3,q,3,q,3,表,3-2,2,转换函数,15/146,7/1/2025,15,3.2有穷状态自动机,将扩充为,对任意,q,Q,，,w,*,，,a,，定义,16/146,7/1/2025,16,3.2有穷状态自动机,两值相同，不用区分这两个符号。,17/146,7/1/2025,17,3.2有穷状态自动机,确定有穷状态自动机,因为对于任意,q,Q,，,a,，,(q,，,a),都有确定值，所以，将这种,FA,称为,确定有穷状态自动机(deterministic finite automaton，DFA),18/146,7/1/2025,18,3.2有穷状态自动机,M,接收,(,识别,),语言,对于,x,*,假如,(q,，,w),F,，则称,x,被,M,接收，假如,(q,，,w),F,，则称,M,不接收,x,。,L(M)=x|x,*,且,(q,，,w),F,称为由,M,接收,(,识别,),语言,L(M,1,)=L(M,2,)=0,2n,|n,1,假如,L(M,1,)=L(M,2,),，则称,M,1,与,M,2,等价。,19/146,7/1/2025,19,3.2有穷状态自动机,例 3-2,结构一个,DFA,，它接收语言为,x000y|x,，,y,0,，,1,*,q,0,M,开启状态；,q,1,M,读到了一个,0,，这个,0,可能是子串“,000,”第,1,个,0,；,q,2,M,在,q,1,后紧接着又读到了一个,0,，这个,0,可能是子串“,000,”第,2,个,0,；,q,3,M,在,q,2,后紧接着又读到了一个,0,，发觉输入字符串含有子串“,000,”；所以，这个状态应该是终止状态。,20/146,7/1/2025,20,3.2有穷状态自动机,(q,0,1)=q,0,M,在,q,0,读到了一个,1,，它需要继续在,q,0,“等候”可能是子串“,000,”第,1,个,0,输入字符,0,；,(q,1,1)=q,0,M,在刚才读到了一个,0,后，读到了一个,1,，表明在读入这个,1,之前所读入,0,并不是子串“,000,”第,1,个,0,，所以，,M,需要重新回到状态,q,0,，以寻找子串“,000,”第,1,个,0,；,21/146,7/1/2025,21,3.2有穷状态自动机,(q,2,1)=q,0,M,在刚才发觉了,00,后，读到了一个,1,，表明在读入这个,1,之前所读入,00,并不是子串“,000,”前两个,0,，所以，,M,需要重新回到状态,q,0,，以寻找子串“,000第,1,个,0,；,(q,3,0)=q,3,M,找到了子串“,000,”，只用读入该串剩下部分。,(q,3,1)=q,3,M,找到了子串“,000,”，只用读入该串剩下部分。,22/146,7/1/2025,22,3.2有穷状态自动机,M=(q,0,，,q,1,，,q,2,，,q,3,，,0,，,1,，,(q,0,0)=q,1,，,(q,1,0)=q,2,，,(q,2,0)=q,3,，,(q,0,1)=q,0,，,(q,1,1)=q,0,，,(q,2,1)=q,0,，,(q,3,0)=q,3,，,(q,3,1)=q,3,，,q,0,，,q,3,),状态说明,状态,输入字符,0,1,开始状态q,0,q,1,q,0,q,1,q,2,q,0,q,2,q,3,q,0,终止状态,q,3,q,3,q,3,23/146,7/1/2025,23,3.2有穷状态自动机,一个更为直观表示,24/146,7/1/2025,24,3.2有穷状态自动机,状态转移图(transition diagram),q,Q,q,是该有向图中一个顶点；,(q,，,a)=p,图中有一条从顶点,q,到顶点,p,标识为,a,弧；,q,F,标识为,q,顶点被用双层圈标出；,用标有,S,箭头指出,M,开始状态。,状态转移图又能够叫做,状态转换图。,25/146,7/1/2025,25,3.2有穷状态自动机,例 3-3,结构一个,DFA,，它接收语言为,x000|x,0,，,1,*,。,状态,q,0,读到,0,可能是输入字符串最终三个,0,第,1,个,0,；,在状态,q,1,紧接着读到,0,可能是输入字符串最终三个,0,第,2,个,0,；,在状态,q,2,紧接着读到,0,可能是输入字符串最终三个,0,第,3,个,0,；,26/146,7/1/2025,26,3.2有穷状态自动机,在状态,q,3,紧接着读到,0,也可能是输入字符串最终三个,0,第,3,个,0,；,假如在状态,q,1,，,q,2,，,q,3,读到是,1,，则要重新检验输入串是否以三个,0,结尾。,27/146,7/1/2025,27,3.2有穷状态自动机,几点值得注意,定义,FA,时，经常只给出,FA,对应状态转移图就能够了。,对于,DFA,来说，并行弧按其上标识字符个数计算，对于每个顶点来说，它出度恰好等于输入字母表中所含字符个数。,28/146,7/1/2025,28,3.2有穷状态自动机,不难看出，字符串,x,被,FA M,接收充分必要条件是，在,M,状态转移图中存在一条从开始状态到某一个终止状态有向路，该有向路上从第,1,条边到最终一条边标识依次并置而组成字符串,x,。简称此路标识为,x。,一个,FA,能够有多于,1,个终止状态。,29/146,7/1/2025,29,3.2有穷状态自动机,接收语言,x000|x,0,，,1,*,x001|x,0,，,1,*,FA,30/146,7/1/2025,30,3.2有穷状态自动机,即时描述(instantaneous description，ID）,x,，,y,*,，,(q,0,，,x)=q,xqy,称为,M,一个,即时描述，,表示,xy,是,M,正在处理一个字符串，,x,引导,M,从,q,0,开启并抵达状态,q,，,M,当前正注视着,y,首字符。,假如,xqay,是,M,一个即时描述，且,(q,，,a)=p,，则,xqay,M,xapy。,31/146,7/1/2025,31,3.2有穷状态自动机,M,n,：表示,M,从即时描述经过,n,次移动抵达即时描述。,M,存在即时描述1,，,2,，,n-1,，使得,M,1,，,1,M,2,，,n-1,M,当n=0时，有=。即,M,0,。,M,+,：表示,M,从即时描述经过最少,1,次移动抵达即时描述。,M,*,：表示M从即时描述经过若干步移动抵达即时描述。,32/146,7/1/2025,32,3.2有穷状态自动机,当意义清楚时，我们将符号,M,、,M,n,、,M,*,、,M,+,中,M,省去，分别用、,n,、,*,、,+,表示。,33/146,7/1/2025,33,3.2有穷状态自动机,对下列图所表示DFA有以下ID转换：,34/146,7/1/2025,34,3.2有穷状态自动机,q,0,1010010001,1q0,010010001,10q,1,10010001,101q,0,0010001,1010q,1,010001,10100q,2,10001,101001q,0,0001,1010010q,1,001,10100100q,2,01,35/146,7/1/2025,35,3.2有穷状态自动机,101001000q,3,1,1010010001q,0,即,q,0,1010010001,10,1010010001q,0,q,0,1010010001,+,1010010001q,0,q,0,1010010001,*,1010010001q,0,36/146,7/1/2025,36,3.2有穷状态自动机,对于,x,*,q,0,x1,+,x1q,0,q,0,x10,+,x10q,1,q,0,x100,+,x100q,2,q,0,x000,+,x000q,3,37/146,7/1/2025,37,3.2有穷状态自动机,能引导,FA,从开始状态抵达,q,字符串集合为：,set(q)=x|x,*,，,(q,0,，,x)=q,对图,3-3,所给,DFA,中全部q，求set(q)。,38/146,7/1/2025,38,set(q,0,)=x|x,*,，,x=,或者,x,以,1,结尾,set(q,1,)=x|x,*,，,x=0,或者,x,以,10,结尾,set(q,2,)=x|x,*,，,x=00,或者,x,以,100,结尾,set(q,3,)=x|x,*,，,x,以,000,结尾,set(q,4,)=x|x,*,，,x,以,001,结尾,这5,个集合是两两互不相交。,39/146,7/1/2025,39,3.2有穷状态自动机,对于任意一个,FA M=(Q,，,q,0,，,F),我们能够按照以下方式定义关系,R,M,：,对,x,，,y,*,，,xR,M,y,q,Q,，使得,x,set(q),和,y,set(q),同时成立。,按照这个定义所得到关系实际上是,*,上一个等价关系。利用这个关系，能够将,*,划分成不多于,|Q|,个等价类。,40/146,7/1/2025,40,3.2有穷状态自动机,例 3-4,结构一个,DFA,，它接收语言为,0,n,1,m,2,k,|n,m,k,1。,q,0,M,开启状态；,q,1,M,读到最少一个,0,，并等候读更多,0,；,q,2,M,读到最少一个,0,后，读到了最少一个,1,，并等候读更多,1,；,q,3,M,读到最少一个,0,后跟最少一个,1,后，而且接着读到了最少一个,2。,41/146,7/1/2025,41,3.2有穷状态自动机,先设计“主体框架”,再补充细节,42/146,7/1/2025,42,3.2有穷状态自动机,当,FA,一旦进入状态,q,t,，它就无法离开此状态。所以，,q,t,相当于一个陷阱状态,(trap),。普通地，我们将陷阱状态用作在其它状态下发觉输入串不可能是该,FA,所识别语言句子时进入状态。在此状态下，,FA,读完输入串中剩下字符。,43/146,7/1/2025,43,3.2有穷状态自动机,在结构一个识别给定语言,FA,时，用画图方式比较方便、直观。我们能够先依据语言主要特征画出该,FA,“主体框架”，然后再去考虑画出一些细节要求内容。,44/146,7/1/2025,44,3.2有穷状态自动机,FA,状态含有一定记忆功效：不一样状态对应于不一样情况，因为,FA,只有有穷个状态，所以，在识别一个语言过程中，假如有没有穷种情况需要记忆，我们必定是无法结构出对应,FA,。,45/146,7/1/2025,45,3.2有穷状态自动机,例 3-5,结构一个,DFA,，它接收语言为,x|x,0,，,1,*,，且当把,x,看成二进制数时，,x,模,3,与,0,同余,。,q,0,对应除以,3,余数为,0,x,组成等价类；,q,1,对应除以,3,余数为,1,x,组成等价类；,q,2,对应除以,3,余数为,2,x,组成等价类；,q,s,M,开始状态。,46/146,7/1/2025,46,3.2有穷状态自动机,q,s,在此状态下读入,0,时，有,x=0,，所以应该进入状态,q,0,；读入,1,时，有,x=1,，所以应该进入状态,q,1,。即：,(q,s,，,0)=q,0,；,(q,s,，,1)=q,147/146,7/1/2025,47,3.2有穷状态自动机,q,0,能引导,M,抵达此状态,x,除以,3,余,0,，所以有：,x=3*n+0,。,读入,0,时，引导,M,抵达下一个状态字符串为,x0,，,x0=2*(3*n+0)=3*2*n+0,。所以，,(q,0,，,0)=q,0,；,读入,1,时，,M,抵达下一个状态字符串为,x1,，,x1=2*(3*n+0)+1=3*2*n+1,。所以，,(q,0,，,1)=q,1,；,48/146,7/1/2025,48,3.2有穷状态自动机,q,1,能引导,M,抵达此状态,x,除以,3,余,1,，所以有：,x=3*n+1,。,读入,0,时，引导M,抵达下一个状态字符串为,x0,，,x0=2*(3*n+1)=3*2*n+2,。所以即：,(q,1,，,0)=q,2,；,读入,1,时，引导,M,抵达下一个状态字符串为,x1,，,x1=2*(3*n+1)+1=3*2*n+2+1=3*(2*n+1),。所以,(q,1,，,1)=q,0,49/146,7/1/2025,49,3.2有穷状态自动机,q,2,能引导,M,抵达此状态,x,除以,3,余,2,，所以：,x=3*n+2,。,读入,0,时，引导,M,抵达下一个状态字符串为,x0,，,x0=2*(3*n+2)=3*2*n+4=3*(2*n+1)+1,。所以,(q,2,，,0)=q,1,；,读入,1,时，引导,M,抵达下一个状态字符串为,x1,，,x1=2*(3*n+2)+1=3*2*n+4+1=3*(2*n+1)+2,。所以，,(q,2,，,1)=q,2,。,50/146,7/1/2025,50,3.2有穷状态自动机,接收语言,x|x,0,，,1,*,，且当把,x,看成二进制数时，,x,模,3,与,0,同余,DFA以下：,51/146,7/1/2025,51,3.2有穷状态自动机,例 3-6,结构一个,DFA,，它接收语言,L=x|x,0,，,1,*,，且对,x,中任意一个长度小于,5,子串,a,1,a,2,a,n,，,a,1,+a,2,+,+a,n,3,，,n,5,。,输入串为a,1,a,2,a,i,a,i+4,a,i+5,a,m,52/146,7/1/2025,52,3.2有穷状态自动机,当,i=1,，,2,，,3,，也就是,M,读到输入串第,1,、,2,、,3,个字符时，它需要将这些字符记下来。因为,a,1,a,i,可能需要用来判定输入串最初,45,个字符组成子串是否满足语言要求。,当,i=4,，,5,，也就是,M,读到输入串第,4,、,5,个字符时，在,a,1,+a,2,+,+a,i,3,情况下，,M,需要将,a,1,a,i,记下来；在,a,1,+a,2,+,+a,i,3,时，,M,应该进入陷阱状态,q,t。,53/146,7/1/2025,53,3.2有穷状态自动机,当,i=6,，也就是,M,读到输入串第,6,个字符，此时，以前读到第,1,个字符,a,1,就没有用了，此时它要看,a,2,+a,3,+,+a,6,3,是否成立，假如成立，,M,需要将,a,2,a,6,记下来；在,a,2,+a,3,+,+a,i,3,时，,M,应该进入陷阱状态,q,t。,54/146,7/1/2025,54,3.2有穷状态自动机,当,M,完成对子串,a,1,a,2,a,i,a,i+4,考查，并发觉它满足语言要求时，,M,记下来是,a,i,a,i+4,，此时它读入输入串第,i+5,个字符,a,i+5,，以前读到第,i,个字符,a,i,就没有用了，此时它要看,a,i+1,a,i+2,+,+a,i+5,3,是否成立，假如成立，,M,需要将,a,i+1,，,a,i+2,，,a,i+5,记下来；在,a,i+1,+a,i+2,+,+a,i+5,3,时，,M,应该进入陷阱状态,q,t。,55/146,7/1/2025,55,3.2有穷状态自动机,M,需要记忆内容有：,什么都未读入,2,0,=1,种；,统计有,1,个字符,2,1,=2,种；,统计有,2,个字符,2,2,=4,种；,统计有,3,个字符,2,3,=8,种；,统计有,4,个字符,2,4,-1=15,种；,统计有,5,个字符,2,5,-6=26,种；,统计当前输入串不是句子,1,种。,56/146,7/1/2025,56,3.2有穷状态自动机,状态设置,q,M,还未读入任何字符；,q,t,陷阱状态；,qa,1,a,2,a,i,M,统计有,i,个字符，,1,i,5,。,a,1,，,a,2,，,a,i,0,，,1,。,取,DFA M=(Q,，,0,，,1,，,q,，,F),F=q,qa,1,a,2,a,i,|a,1,，,a,2,，,a,i,0,，,1,且,1,i,5,且,a,1,+a,2,+,+a,i,3,Q=q,t,F,57/146,7/1/2025,57,3.2有穷状态自动机,(q,，,a,1,)=qa,1,(qa,1,，,a,2,)=qa,1,a,2,(qa,1,a,2,，,a,3,)=qa,1,a,2,a,3,qa,1,a,2,a,3,a,假如,a,1,+a,2,+a,3,+a,3,(qa,1,a,2,a,3,，,a)=,q,t,假如,a,1,+a,2,+a,3,+a3,58/146,7/1/2025,58,3.2有穷状态自动机,qa,1,a,2,a,3,a,4,a,假如,a,1,+a,2,+a,3,+a,4,+a,3,(qa,1,a,2,a,3,a,4,，,a)=,q,t,假如,a,1,+a,2,+a,3,+a,4,+a3,qa,2,a,3,a,4,a,5,a a,2,+a,3,+a,4,+a,5,+a,3,(qa,1,a,2,a,3,a,4,a,5,，,a)=,q,t,假如,a,2,+a,3,+a,4,+a,5,+a3,(q,t,，,a,1,)=q,t,59/146,7/1/2025,59,3.3 NFA,3.3.1 作为对DFA修改,希望是接收,x|x,0,，,1,*,，且,x,含有子串,00,或,11,FA以下：,60/146,7/1/2025,60,3.3.1 作为对DFA修改,希望是接收,x|x,0,，,1,*,，且,x,倒数第,10,个字符为,1,FA以下,：,61/146,7/1/2025,61,3.3.1 作为对DFA修改,这两个图所给“,FA,”与前面我们所定义,FA,，即,DFA,，区分在于：,并不是对于全部,(q,，,a),Q,(q,，,a),都有一个状态与它对应；,并不是对于全部,(q,，,a),Q,(q,，,a),只对应一个状态。,“,FA,”在任意时刻能够处于有穷多个状态。,“,FA,”含有“智能”,。,62/146,7/1/2025,62,3.3.2 NFA形式定义,不确定有穷状态自动机(non-deterministic finite automaton,NFA),M是一个五元组,M=(Q，q,0,，F),Q、q,0,、F意义同DFA。,：Q,2,Q,，对,(q，a)Q，(q，a)=p,1,，p,2,，p,m,表示M在状态q读入字符a，能够选择地将状态变成p,1,、或者p,2,、或者p,m,，并将读头向右移动一个带方格而指向输入字符串下一个字符。,63/146,7/1/2025,63,3.3.2 NFA形式定义,FA状态转移图、FA状态对应等价类、FA即时描述对NFA都有效。,接收,x|x,0,，,1,*,，且,x,含有子串,00,或,11,FA对应移动函数定义表。,64/146,7/1/2025,64,3.3.2 NFA形式定义,状态说明,状态,输入字符,0,1,开启状态,q,0,q,0,，q,1,q,0,，q,2,q,1,q,3,q,2,q,3,终止状态,q,3,q,3,q,3,65/146,7/1/2025,65,3.3.2 NFA形式定义,接收,x|x,0,，,1,*,，且,x,倒数第,10,个字符为,1,FA对应移动函数定义表。,66/146,7/1/2025,66,3.3.2 NFA形式定义,状态说明,状态,输入字符,0,1,开启状态,q,0,q,0,q,0,，,q,1,q,1,q,2,q,2,q,2,q,3,q,3,q,3,q,4,q,4,q,4,q,5,q,5,q,5,q,6,q,6,q,6,q,7,q,7,q,7,q,8,q,8,q,8,q,9,q,9,q,9,q,10,q,10,终止状态,q,10,67/146,7/1/2025,67,3.3.2 NFA形式定义,将扩充为,对任意,q,Q,，,w,*,，,a,，定义,68/146,7/1/2025,68,3.3.2 NFA形式定义,和关于DFA结论一样，两值相同，也不用区分这两个符号。,69/146,7/1/2025,69,3.3.2 NFA形式定义,深入扩充定义域：,2,Q,*,2,Q,。对任意,P,Q,，,w,*,70/146,7/1/2025,70,3.3.2 NFA形式定义,因为，对,(q,，,w),Q,*,所以，不一定严格地域分第,1,个分量是一个状态还是一个含有一个元素集合。,71/146,7/1/2025,71,3.3.2 NFA形式定义,对任意,q,Q,，,w,*,，,a,：,(q,，,wa)=,(,(q,，,w),，,a),对输入字符串,a,1,a,2,a,n,(q,，,a,1,a,2,a,n,)=,(,q,a,1,),a,2,),，,),，,a,n,),。,72/146,7/1/2025,72,3.3.2 NFA形式定义,M,接收,(,识别,),语言,对于,x,*,，,假如,(q,0,，,w),F,，则称,x,被,M,接收，假如,(q,0,，,w),F=,，则称,M,不接收,x,。,L(M)=x|x,*,且,(q,0,，,w),F,，,称为由,M,接收,(,识别,),语言。,73/146,7/1/2025,73,3.3.3 NFA与DFA等价,对于一个输入字符，,NFA,与,DFA,差异是前者能够进入若干个状态，而后者只能进入一个惟一状态。即使从,DFA,对待问题角度来说，,NFA,在某一时刻同时进入若干个状态，不过，这若干个状态合在一起“总效果”相当于它处于这些状态对应一个“综合状态”。所以，我们考虑让,DFA,用一个状态去对应,NFA,一组状态。,74/146,7/1/2025,74,3.3.3 NFA与DFA等价,NFA M,1,=(Q,，,1,，,q,0,，,F,1,),与,DFA M,2,=(Q,2,，,2,，,q,0,，,F,2,),对应关系：,NFA,从开始状态,q,0,开启，我们就让对应,DFA,从状态,q,0,开启。所以,q,0,=q,0,。,对于,NFA,一个状态组,q,1,，,q,2,，,q,n,，假如,NFA,在此状态组时读入字符,a,后能够进入状态组,p,1,，,p,2,，,p,m,则让对应,DFA,在状态,q,1,，,q,2,，,q,n,读入字符,a,时，进入状态,p,1,，,p,2,，,p,m,。,75/146,7/1/2025,75,3.3.3 NFA与DFA等价,定理 3-1,NFA,与,DFA,等价。,证实：,结构与,M,1,等价,DFA M,2,。,M,1,=(Q,，,1,，,q,0,，,F,1,),M,2,=(Q,2,，,2,，,q,0,，,F,2,),Q,2,=2,Q,F,2,=p,1,，,p,2,，,p,m,|p,1,，,p,2,，,p,m,Q&p,1,，,p,2,，,p,m,F,1,76/146,7/1/2025,76,3.3.3 NFA与DFA等价,2,(q,1,，,q,2,，,q,n,，,a)=p,1,，,p,2,，,p,m,1,(q,1,，,q,2,，,q,n,，,a)=p,1,，,p,2,，,p,m,(2),证实,1,(q,0,，,x)=p,1,，,p,2,，,p,m,2,(q,0,，,x)=p,1,，,p,2,，,p,m,。,设,x,*,，施归纳于,|x|,x=,，,1,(q,0,，,)=q,0,2,(q,0,，,)=q,0,77/146,7/1/2025,77,3.3.3 NFA与DFA等价,设当,|x|=n,是结论成立。下面证实当,|x|=n+1,是结论也成立。不妨设,x=wa,，,|w|=n,，,a,1,(q,0,，,wa)=,1,(,1,(q,0,，,w),，,a),=,1,(q,1,，,q,2,，,q,n,，,a),=p,1,，p,2,，p,m,由归纳假设，,1,(q,0,，w)=q,1,，q,2,，q,n,2,(q,0,，w)=q,1,，q,2,，q,n,78/146,7/1/2025,78,3.3.3 NFA与DFA等价,依据,2,定义，,2,(q,1,，,q,2,，,q,n,，,a)=p,1,，,p,2,，,p,m,1,(q,1,，,q,2,，,q,n,，,a)=p,1,，,p,2,，,p,m,所以，,2,(q,0,，,wa)=,2,(,2,(q,0,，,w),，,a),=,2,(q,1,，,q,2,，,q,n,，,a),=p,1,，,p,2,，,p,m,79/146,7/1/2025,79,3.3.3 NFA与DFA等价,故，假如,1,(q,0,，,wa)=p,1,，,p,2,，,p,m,则必有,2,(q,0,，,wa)=p,1,，,p,2,，,p,m,。,由上述推导可知，反向推导也成立。这就是说，结论对,|x|=n+1,也成立。,由归纳法原理，结论对,x,*,成立。,80/146,7/1/2025,80,3.3.3 NFA与DFA等价,(3),证实,L(M,1,)=L(M,2,),设,x,L(M,1,),，且,1,(q,0,，,x)=p,1,，,p,2p,m,，,从而,1,(q,0,，,x),F,1,这就是说，,p,1,，,p,2,，,p,m,F,1,，,由,F,2,定义，,p,1,，,p,2,，,p,m,F,2,。,81/146,7/1/2025,81,3.3.3 NFA与DFA等价,再由,(2),知，,2,(q,0,，,x)=p,1,，,p,2,，,p,m,所以，,x,L(M,2,),。故,L(M,1,),L(M,2,),。,反过来推，可得,L(M,2,),L(M,1,),。,从而,L(M,1,)=L(M,2,),得证。,总而言之，定理成立。,82/146,7/1/2025,82,例 3-7,图,3-9,所表示,NFA,对应,DFA,状态转移函数如表,3-7,所表示。,图,3-9,83/146,7/1/2025,83,表,3-7,状态转移函数,状态说明,状态,输入字符,0,1,开启,q,0,q,0,q,1,q,0,q,2,q,1,q,3,q,2,q,3,终止,q,3,q,3,q,3,q,0,q,1,q,0,q,1,q,3,q,0,q,2,q,0,q,2,q,0,q,1,q,0,q,2,q,3,终止,q,0,q,3,q,0,q,1,q,3,q,0,q,2,q,3,q,1,q,2,q,3,q,3,终止,q,1,q,3,q,3,q,3,终止,q,2,q,3,q,3,q,3,q,0,q,1,q,2,q,0,q,1,q,3,q,0,q,2,q,3,终止,q,0,q,1,q,3,q,0,q,1,q,3,q,0,q,2,q,3,终止,q,0,q,2,q,3,q,0,q,1,q,3,q,0,q,2,q,3,终止,q,1,q,2,q,3,q,3,q,3,终止,q,0,q,1,q,2,q,3,q,0,q,1,q,3,q,0,q,2,q,3,84/146,7/1/2025,84,3.3.3 NFA与DFA等价,不可达状态(inaccessible state)：,不存在从q,0,对应顶点出发，抵达该状态对应顶点路。我们称此状态从开始状态是不可达。,表,3-7,中，全部标识“,”状态是从开始状态可达，其它是不可达无用。,85/146,7/1/2025,85,3.3.3 NFA与DFA等价,结构给定,NFA,等价,DFA,策略,先只把开始状态,q,0,填入表状态列中，假如表中所列状态列有未处理，则任选一个未处理状态,q,1,，,q,2,，,q,n,，对中每个字符,a,，计算,(q,1,，,q,2,，,q,n,，,a),，并填入对应表项中，假如,(q,1,，,q,2,，,q,n,，,a),在表状态列未出现过，则将它填入表状态列。如此重复下去，直到表状态列中不存在未处理状态。,86/146,7/1/2025,86,3.3.3 NFA与DFA等价,图,3-11,图,3-9,所表示,NFA,等价,DFA,87/146,7/1/2025,87,3.4 带空移动有穷状态自动机,接收语言0,n,1,m,2,k,|n，m，k0NFA,88/146,7/1/2025,88,3.4 带空移动有穷状态自动机,接收语言0,n,1,m,2,k,|n，m，k0NFA是否能够结构成下列图所表示“-NFA,”？,其结构显然比图1-13所表示NFA更轻易。当然还希望它们是等价。,89/146,7/1/2025,89,3.4 带空移动有穷状态自动机,带空移动不确定有穷状态自动机(non-deterministic finite automaton with-moves,-NFA),M=(Q，q,0,，F)，Q、q,0,、F意义同DFA。,：Q(),2,Q,90/146,7/1/2025,90,3.4 带空移动有穷状态自动机,非空移动,(q，a)Q,(q，a)=p,1,，p,2,，p,m,表示M在状态q读入字符a，能够选择地将状态变成p,1,、p,2,、或者p,m,，并将读头向右移动一个带方格而指向输入字符串下一个字符。,91/146,7/1/2025,91,3.4 带空移动有穷状态自动机,空移动,qQ,(q，)=p,1,，p,2,，p,m,表示M在状态q不读入任何字符，能够选择地将状态变成p,1,、p,2,、或者p,m,。也能够叫做M在状态q做一个空移动(又能够称为移动)，而且选择地将状态变成p,1,、p,2,、或者p,m,。,92/146,7/1/2025,92,3.4 带空移动有穷状态自动机,深入扩充定义域：,2,Q,*,2,Q,。对任意,P,Q,，,w,*,。,对任意,q,Q,，,w,*,，,a,。,-CLOSURE(q)=p|,从,q,到,p,有一条标识为路,。,93/146,7/1/2025,93,3.4 带空移动有穷状态自动机,94/146,7/1/2025,94,3.4 带空移动有穷状态自动机,深入扩展移动函数：,2,Q,2,Q,。,对任意,(P,，,a),2,Q,。,95/146,7/1/2025,95,3.4 带空移动有穷状态自动机,在,-NFA,中，对任意,a,，,q,Q,，,需要严格区分。,96/146,7/1/2025,96,图,3-14,所表示,-NFA,状态,0,1,2,0,1,2,q,0,q,1,q,0,q,0,q,1,q,2,q,0,q,1,q,2,q,1,q,2,q,2,q,1,q,2,q,1,q,1,q,2,q,1,q,2,q,2,q,2,q,2,q,2,q,2,97/146,7/1/2025,97,3.4 带空移动有穷状态自动机,M,接收,(,识别,),语言,对于,x,*,，仅当,时，称,x,被,M,接收。,98/146,7/1/2025,98,3.4 带空移动有穷状态自动机,定理 3-2,-NFA,与,NFA,等价。,证实：设有,-NFA,M,1,=(Q,，,1,，,q