第03章 有穷状态自动机 - 电子科技大学.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,即时描述,设,M,=(,Q,q,0,F,),为一个,FA,，,x,y,*,，,(,q,0,x,)=,q,，,xqy,称为,M,的一个,即时描述。,它表示,xy,是,M,正在处理的一个字符串，,x,引导,M,从,q,0,启动并到达状态,q,，当前正指向,y,的首字符。,如果,xqay,是,M,的一个,即时描述,，且,(,q,a,)=,p,，,则经过字符,a,的处理后，,即时描述,变为,xapy,。,这一过程记作：,xqay,xapy,DFA,的构造,设,M,=(,Q,q,0,F,),为一个,FA,，对,q,Q能引导,FA,从开始状态到达,q,的字符串的集合为,set,(,q,)=,x,|,x,*,(,q,0,x,)=,q,出现语言不能接受的序列时进入陷井状态,q,t,构造语言的,DFA,。,3.3,不确定的有穷状态自动机,作为对,DFA,的修改,构造接受语言,L=,x,|,x,0,1,*,且,x,含有子串,00,或,11,的,DFA,S,q,0,0,q,1,q,2,q,3,0,1,1,0,1,1,0,“直接”的,FA,S,q,0,0,q,1,q,2,q,3,0,0,1,0,1,1,1,希望是接受语言,L=,x,|,x,0,1,*,且,x,含有子串,00,或,11,的,FA,与,DFA,的区别,并不是对于所有的,(,q,a,),Q,，,(,q,a,),都有一个状态与之对应,(,相当于,f,(,x,),对某些,x,没有函数值,),；,并不是对于所有的,(,q,a,),Q,，,(,q,a,),都只对应一个状态,(,相当于,f,(,x,),对某些,x,有多个函数值,),。,理解这种“,FA”,(,q,a,),对应的是状态的一个子集，即,x,2,Q,。,当这个子集为空时，表示没有状态与之对应；,当这个子集的元素个数大于,1,时，表示有多个状态与之对应。,当这个子集元素个数为,1,时，退化为,DFA,。,从这个意义上，,(,q,a,),仍是通常意义下的一个函数，只是其值域发生了改变。,这种“,FA”,的特点,S,q,0,0,q,1,q,2,q,3,0,0,1,0,1,1,1,具有“智能”：可根据当前从输入字符串读入的,字符自动地选择进入一个正确的状态。,这种“,FA”,的特点,具有“智能”,只要在,FA,中,存在一条,从开始状态出发，最终到达某一个终止状态的标记为,x,的路径，就认为它接受了串,x,，,否则认为它不接受串,x,。,从这个意义上来说，这类,FA,与,DFA,的作用是一致的,(,识别句子是否合法,),。,NFA,的形式定义,定义,3-7,不确定的有穷状态自动机,(non-deterministic finite automaton,NFA),M,是一个五元组：,M,=(Q,q,0,F,),其中，,Q,q,0,F,状态的意义同,DFA(,定义,3-1,),状态转移函数,。,:,Q,2,Q,。,对,(,q,a,),Q,，,(,q,a,)=,p,1,p,2,p,m,表示,M,在状态,q,读入字符,a,，,可以选择地将状态变成,p,1,p,2,或者,p,m,，,并将读头向右移动一个带方格而指向输入字符串的下一个字符。,扩充,将,扩充为,：,Q,*,2,Q,。,对,q,Q,，,w,*,，,a,：,(1),(,q,)=,q,(2),(,q,wa,)=,p,|,r,(,q,w,),st,.,p,(,r,a,),扩充的作用：,(1),加入单位元素,(2),从概念上允许一次接收字母表的任意一个字符串，而不仅是一个字符,与,“兼容”,的定义域,Q,是 的定义域的,Q,*,真子集，需要考虑在上,Q,，,是否与,有相同的函数值,：,(,q,a,)=(,q,a,),=,p,|,r,(,q,),st,.,p,(,r,a,),根据,(2),=,p,|,r,q,st,.,p,(,r,a,),根据,(1),=,p,|,p,(,q,a,),q,是,r,唯一可能值,=,(,q,a,),因此 与,“兼容”。约定：,以后直接用,代替,。,进一步,扩充,将,进一步,扩充为,:,2,Q,*,2,Q,。对,P,Q,，,w,*,:,(,P,w,)=,(,q,w,),扩充的意义：从概念上可以处理一个状态集合对某一字符串的“反应”。如：模,4,余,0,的例子中，无论是什么状态下接收了,00,，都会转到,q,0,。,更深的意义可借助定理,3-1,的证明及例,3-7,体会。,定义,3-8,设,M,=(,Q,q,0,F,),为一个,NFA,。对于,x,*,：,如果,(,q,0,x,),F,，,则称,x,被,M,所接受；如果,(,q,0,x,),F,=,，,则称,M,不接受,x,。,L,(,M,)=,x,|,x,*,且,(,q,0,x,),F,称为由,M,接受,(,识别,),的语言。,练习,(,见习题,),10.(1),构造识别语言,L=,x,|,x,0,1,+,且,x,中不含形如,00,的,子串的,NFA,习题评讲,10.(1),S,q,0,q,2,0,1,0,0,1,0,q,1,本答案错误，因为任意串均可以到达,q,0,习题评讲,(,续,),10.(1),正确答案与,2.(3),相同，因为,DFA,是,NFA,的特例,(,把状态,q,3,去掉也可以,),S,q,0,1,q,1,1,0,1,q,3,0,q,2,0,0,1,分析,NFA,适于构造“包含子串,”,，“以串,开始，串,结束”，“,(,倒数,),第,个字母是,”,，“满足条件,”,的语言；,NFA,不适于构造“不包含子串,”,，“不满足条件,”,的语言，在这些情况下它可能退化为,DFA,。,定理,3-1,NFA,与,DFA,等价。,NFA,与,DFA,等价,是指,NFA,和,DFA,能识别相同的语言类。,回顾,等价,的概念：识别相同的语言,(,定义,3-3),。,证明思路,(1),显然，,DFA,是,NFA,的特殊形式；即所有的,DFA,已经用,NFA,的形式表示；,(2),需要证明对于任意给定的,NFA,，,存在与之等价的,DFA,。,根据,NFA,构造,DFA,，,将状态集合从,Q,变换到,2,Q,，这样,DFA,中的任意一个状态实际上是,NFA,中某些状态的组合,(,这里避免使用术语“集合”,),。,使用归纳法证明,DFA,与,NFA,的状态转移存在一一对应关系。,证明由,DFA,和,NFA,能识别相同的语言。,L,(,M,1,)=,L,(,M,2,),例,3-7,求与下图所示,NFA,等价的,DFA,。,S,q,0,0,q,1,q,2,q,3,0,0,1,0,1,1,1,例,3-7(,续,),从,q,0,开始可以到达的状态为可达状态,对于,DFA,来说，只有可达状态才有用。,分析：,DFA,的一个状态对应,NFA,的一个状态集合，因此，需要,2,4,=16,个状态。下表列出其状态转移。,例,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,q3,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,例,3-7(,续,),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,1q,2,q,3,q,0,q,1,q,3,q,0,q,2,q,3,例,3-7(,续,),获得的,DFA,。,S,q,0,0,q,0,q,1,0,0,1,1,q,0,q,2,1,0,q,0,q,1,q,3,0,1,q,0,q,2,q,3,1,例,3-7(,续,),简化后的,DFA,。,S,q,0,0,q,1,q,2,q,3,0,1,1,0,1,1,0,例,3-7(,续,),减少工作量的方法,只列出可达状态的转移，即填表时不需要填完,填表时可用,0,1,代替,q,0,q,1,总是不可达的，可将该状态对应的转移去掉,说明,这种记法主要是为了保持上下文一致，实际上它与,q,0,q,1,应有所区别。,练习,(,见习题,),11.(1)(,去掉输入字母,2),要求：,画出,NFA,状态转移图；,构造,DFA,，,获取其转移函数；,画出状态转移图；,化简,DFA,。,NFA,的状态转移函数如下，构造与之等价的,DFA,状态说明,状态,输入字符,0,1,开始状态,q,0,q,0,q,1,q,0,q,2,q,1,q,3,q,0,q,2,q,3,q,1,终止状态,q,3,q,3,q,2,q,3,习题评讲,(,续,),NFA,S,q,0,0,q,1,0,1,1,q,2,q,3,0,1,0,1,0,0,1,习题评讲,状态说明,状态,输入字符,0,1,开始状态,q,0,q,0,q,1,q,0,q,2,q,1q,3,q,0,q,2,q,3,q,1,终止状态,q,3,q,3,q,2,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,1,q,2,q,3,终止状态,q,0,q,3,q,0,q,1,q,2,q,3,q,0,q,2,q,3,习题评讲,(,续,),q,1,q,2,q,0,q,3,q,3,q,1,终止状态,q,1,q,3,q,0,q,2,q,3,q,0,q,2,终止状态,q,2,q,3,q,2,q,3,q,1,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,0,1,2,3,q,0,q,2,q,3,终止状态,q,0,q,2,q,3,0,1,2,3,0,1,2,3,终止状态,q,1,q,2,q,3,q,0,q,2,q,3,q,1,q,3,终止状态,q,0,q,1,q,2,q,3,0,1,2,3,0,1,2,3,习题评讲,(,续,),DFA,S,q,0,0,q,0,q,1,0,1,1,q,0,q,2,1,0,q,0,q,1,q,3,0,q,0,q,1,q,2,q,3,0,1,1,q,0,q,2,q,3,0,1,习题评讲,(,续,),化简后的,DFA,S,q,0,0,q,1,q,2,q,3,0,1,1,0,1,1,0,作业,(,见习题,),10.(2)(5),