有限自动机理论CH3PART1.ppt

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第三章,有限状态自动机,定义语言,可以从两个方面,进行,：,）从,产生,语言的角度；,）从,接收,(,或识别,),语言的角度。,形式语言研究内容,产生,一个语言,:,1),定义语言中的,基本句子,;,2),根据,其余句子,的,形成规则,，,产生,出该语言所包含的所有,句子,。,有限自动机,研究内容,使用某种,自动机模型,来接收字符串,接收,的所有字符串形成的集合，也是一个语言,统一的理论,形式语言与自动机作为统一的理论,实际上包括,3,个方面的内容,:,1),形式语言,理论,(,产生语言,),2),自动机,理论,(,接收语言,),3),形式语言与自动机的,等价性,理论,有限状态自动机,FA(,F,inite state,A,utomaton),FA,是为研究,有限,存储,的计算过程,正则,语言,而抽象出的一种计算模型。,两,类有限状态自动机,接,收,器,判断是否,接,收,输入,串,；,转换器,对给定输入,产生输出,。,FA,还可以分成,确定,（,DFA,）,与,非确定,（,NFA,）,两种。,等价性,有限状态自动机识别的语言称为,有限状态语言,-FSL,.,从产生语言角度而言，,FSL,就是,右线性语言,-,RLL,从正则运算角度而言，,FSL,就是,正则语言,-,RL,。,有限状态自动机除了它在理论上的价值,外,，,还在,数字电路,设计,、,词法分析,、,文本编辑程序,等领域得到,广泛,应用,3.1,有限状态自动机,有限状态自动机是具有,离散,输入和输出系统的一种,数学模型,。,有限状态自动机,物理模型,a,1,a,2,a,3,a,j,a,n,a,n,+1,FSC,一个输入,存储带（输入带）,，带被分解为,单元,，每个单元存放一个输入符号,(,字母表上的符号,),。,整个输入串从带的左端点开始存放，而带的右端可以,无限扩充,；,一个有穷状态控制器（,FSC,）,该控制器的状态只能是有限多个,FSC,通过一个,读头,读出,当前带上单元的字符。,初始时，读头对应带的,最左单元,，每读出一个字符，读头,向右,自动移动一个单元。,读头,(,暂时,),不,允许,向左移动,。,有限状态自动机的一个动作为：,读头,读出,带上当前单元的字符,FSC,根据当前,FSC,的状态和读出的字符，,进行,状态改变,；,将读头,向右移动,一个单元。,有限态自动机的动作,简化,为：,FSC,根据,当前状态,和,当前读取的带上,字符,进行,状态改变,。,定义,3-1,有限状态自动机,FA,FA,是一个五元式,FA=(,Q,，,，,，,q,0,，,F),Q,是有限状态的集合,是字母表，也就是输入带上的字符的集合；,q,0,Q,是开始状态；,F,Q,是接收状态,(,终止状态,),集合；,是,Q,Q,的状态转换函数，,即,(q,，,x),=,q,代表自动机在状态,q,时，扫描字符,x,后到达状态,q,有限状态自动机的状态转换函数的个数应该为,|Q|*|,对于,Q,中的每个,状态,，都应该定义对应,的每个,字母,的,状态转换,。,DFA,这种有限状态自动机为,确定的有限状态自动机,DFA,。,例,3-1,DFA,=(q,0,q,1,0,1,q,0,q,0,),其中,：,的表示：函数形式,(q,0,，,0)=,q,1,(q,0,，,1)=q,1,(q,1,，,0)=q,1,(q,1,，,1)=,q,0,的表示：状态矩阵,Q,0,q,0,1,q,1,q,1,q,1,q,1,q,0,的表示,:,状态图形式,状态图是一个,有向,、有,循环,的图,一个节点表示一个状态；若有,(q,，,x,)=q,，,则,状态,q,到状态,q,有一条,有向边,，并用字母,x,作标记。,的表示,指向的状态是开始状态,两个圆圈,代表,接收状态,；,的表示：,状态图,q,1,1,0,1,0,q,0,用状态图表示一个,DFA,有向边的,数目,就是状态转换函数的个数。,3.2,有限状态自动机识别语言,对于,DFA,，给定串,w=x,1,x,2,x,n,；,初始时，,DFA,处于开始状态,q,0,从左到右逐个字符地扫描串,w,在,(q,0,，,x,1,)=q,1,的作用下,DFA,处于状态,q,1,在,(q,1,，,x,2,)=q,2,的的作用下,DFA,处于状态,q,2,当将串,w,扫描结束,后，,若,DFA,处于某一个,接收状态,，,则有限状态自动机能够,接收,串,w,对于,可接收串,DFA,从,开始状态,开始，在扫描,串,的过程中，,状态逐个地变化,串扫描结束后，,到达,某个,接收状态,。,对于,不可接收串,DFA,从,开始状态,开始，在扫描,串,的过程中，,状态逐个地变化,串扫描结束后，,处于,非接收状态,。,对于字母表上的,DFA,能识别的所有串的集合，就是,DFA,能接收的语言,:,L(DFA),也称为有限状态语言（,FSL,）,思考,如何,形式化,定义,L(DFA),?,定义,3-4,扩展的状态转换函数,给定,DFA,，扩展的状态转换函数,*,：,Q,*,Q,即,*,(,q,w,)=q,即,DFA,在一个状态,q,时，扫描串,w,后到达唯一,确定,的状态,q,递归,扩展的状态转换函数,*,(,q,)=,q,；,*,(,q,a,)=,(q,a,),其中,a,；,对于串,w=,a,（,+,）,*,（,q,，,w,）,=,*,(q,，,a,）,=,(,*,(,q,),a,),或者,对于串,w=,a,*,(q,，,w,),=,*,(q,，,a,),=,*,(,(q,，,a,),),定义,3-6 DFA,接收的语言,DFA=(Q,q,0,，,F),接收的语言,L(DFA)=,w|,*,(q,0,w),F,思考,如何描述,在某个,时刻,，,DFA,所处的情况？,定义,3-7 DFA,的瞬时描述（格局）,格局是一个二元式：,q,y,q,是,DFA,当前状态,y,是输入带上还没有被扫描到的串,读头将扫描,y,串的第,1,个符号,在扫描串的过程中，格局在发生转换,(,改变,),格局的,(,一次,),转换的原因是由于,函数,的,(,一次,),作用,如果当前格局为：,q,a,r,有,函数：,(q,，,a)=q,则下一格局为：,qr,；,格局的转换可以记为：,qar,=,qr,；,DFA,的特殊格局,初始格局为：,q,0,w,接收格局为：,q,f,其中，,q,f,是某个接收状态,使用,=,*,代表格局的,任意次,转换,使用,=,+,代表格局的,多次,转换,可以使用,格局的转换,方式定义,FSL,DFA,接收的语言,L(DFA)=,w|q,0,w=,*,q,f,；,w,*,且,q,f,F,定义,3-8 DFA,停机,DFA,将输入串扫描结束时,(,自动,),停机,注意,1,：,DFA,将输入串扫描结束停机时，,如果,DFA,处于某一个,接收状态,，则表示接收整个输入串；,反之，则表示,不接收,整个输入串,;,注意,2,：,对于状态,q,如果,不能识别,字母,a,则将状态转换到一个特殊的状态：,陷阱状态,q,t,即,(q,，,a)=,q,t,陷阱,状态,q,t,不能够改变为其他状态,即 对于,a,(,q,t,，,a)=,q,t,构造,DFA,，分别接收语言,0,，,1,*,0,，,1,+,0,=0,01,定理,3-1,每个,FSL,都是一个,右线性语言,分析：,已知 接收,FSL,的,DFA,构造,右线性文法,产生该,FSL,证明思路,状态转换函数和产生式的,等价,作用,(q,a,)=q,A,a,B,接收,a,产生,a,状态,变化,非终结符号,变化,结论,:DFA,状态,等价于文法,非终结符,思考,DFA,的接收状态的作用,证明,假设,L,是字母表上的,FSL,，则,L=L(DFA),DFA=,（,Q,，,，,q,0,，,F,）,构造,右线性,文法,G=(,Q,q,0,，,P,）,其中,P,为：,qaq,|(q,，,a)=q,U,q,a,|(q,，,a)F,特别，若,q,0,是接收状态，则,q,0,对于串,w=x,1,x,2,x,n,：,DFA,：,则文法有,(q,0,x,1,)=q,1,q,0,x,1,q,1,；,(q,1,x,2,)=q,2,q,1,x,2,q,2,；,(q,n-2,x,n-1,)=q,n-1,q,n-2,x,n-1,q,n-1,(q,n-1,x,n,)=,q,n,q,n-1,x,n,q,n,或,q,n-1,x,n,所以,DFA,文法,*,(q,，,)=q q=,*,q,*,(q,0,，,w)F,q,0,=,*,w,例,3-2 DFA,与文法的转换,FSL,=(0,1)1,*,0,*,接收该语言的,DFA,为：,q,1,1,0,0,1,q,0,构造,正则,文法产生该语言：,q,0,0q,1,|1q,1,|,q,1,0q,0,|1q,1,|,0,定理,3-2,FSL,对,补,运算封闭,证明：,设,L,1,是上的,FSL,且,L,1,=L(DFA,1,),，,DFA,1,=,（,Q,，,，,q,0,，,F,）,构造,DFA,2,=,（,Q,，,，,q,0,，,Q,）,DFA,2,接收的语言是,L,1,的对应的全集,即,*,构造,DFA,3,=(Q,，,，,q,0,，,Q-F,),DFA,3,接收的语言是,L,1,的,补,L,3,=L(DFA,3,),也是,FSL,语言。,注意,此时的,DFA,1,的,函数的个数为,|Q|,*,|,基本的等价替换,对于状态转换图，有基本的等价替换,变换为,0,0,1,1,3.3 DFA,识别语言的例子,构造,DFA,，,接收语言,L=,ab,基本结构（接收基本句子）,q,1,a,b,q,0,q,2,增加,陷阱状态,后的,DFA,q,1,a,b,q,0,q,t,b,a,a,b,a,b,q,2,思考,1,如果将该,DFA,的,所有状态,都设置为,接收状态,(,包括陷阱状态,),，,接收的语言是,？,思考,2,如果将该自动机的接收状态和非接收,状态对调,接收的语言是,？,例,3-4,构造,DFA,识别语言,L=,x000y,|x,y0,1,*,分析,该语言的特点是,语言中的每个串都包含连续的,3,个,0,（即每个串都包含子串,000,）,因此，对于任何输入串，有限状态自动机的任务就是要,检查,该输入串中是否存在子串,000,，,一旦发现输入串包含有,000,，则表示,整个输入串,是,句子,。,因此，在确认输入串包含,000,后，,就可以逐一地读入,000,后面的全部字符，并接收该输入串。,思考,问题的关键是,？,如何,发现,子串,000,。,由于字符是逐一读入的，当从输入串中读入一个,0,时，,它,有可能,是,000,的,第,1,个,0,，,需要,记住,已经出现过一个,0,；,如果紧接着读入的是字符,1,，,则刚读入的,0,就不是,000,的第,1,个,0,需要,重新寻找,000,子串的第,1,个,0,；,如果紧接着读入的还是,0,，它,有可能,是,000,的,第,2,个,0,，,也需要,记住,这个,0,，,继续读入字符，若是,0,，则,发现,000,否则，需要,重新,寻找,000,。,初始状态：,q,0,接收,0,，到达状态,q,1,接收,00,到达状态,q,2,接收,000,到达状态,q,3,因此，,基本的,状态转移函数为：,(q,0,，,0)=q,1,(q,1,，,0)=q,2,(q,2,，,0)=q,3,用于接收基本句子,000,接收,000,的状态图,q,0,0,0,0,q,1,q,2,q,3,其他状态转移函数为：,(q,0,，,1)=q,0,期待,0,的出现,(q,1,，,1)=q,0,重新寻找,000,(q,2,，,1)=q,0,重新寻找,000,(q,3,，,0)=q,3,扫描后续字符,(q,3,，,1)=q,3,扫描后续字符,状态转移图,q,0,0,1,1,1,0,0,0,1,q,1,q,2,q,3,思考,如果需要接收语言,L,如何修改有限状态自动机,?,思路：,考虑,开始状态,的作用,思考,:,如果,DFA,的,开始状态,只负责识别输入串的第一个字母；,文法的,开始符号,只负责串的推导的开始；,优点是？,状态图为,1,0,q,s,0,1,0,0,0,1,q,1,q,2,q,3,q,0,1,1,例,3-5,构造,DFA,识别语言,L=,x,001,y,|x,，,y0,，,1,*,分析：,对于任何输入串，,DFA,的任务就是要检查该输入串中是否存在,001,初始状态：,q,0,q,1,已接收,0,q,2,已接收,00,q,3,已接收,001,q,2,q,1,q,0,状态转移图,0,1,q,3,1,0,1,0,1,0,例,3-6,构造,DFA,识别语言,L=,x,000,|x0,，,1,*,q,2,q,3,q,1,q,0,0,1,1,1,0,0,0,1,例,3-7,构造,DFA,识别语言,L=,x,000,x,001,其中，,x0,，,1,*,q,2,q,1,q,0,0,1,q,3,1,0,0,0,1,q,4,1,0,1,例,3-8,构造,DFA,识别语言,L=,0,2k+3m,|m,k=0,实际上：,2k+3m,可以表示任意的,非负整数,(,除,1,外,),该语言为,0*-0,状态转移图,0,0,0,q,1,q,2,q,0,思考：,构造,DFA,识别语言,L=0,2k+3m,|,m,k0,考查题,1,例,3-9,构造,DFA,识别,0,，,1,上的语言，该语言的,每个句子以,0,开头，以,1,结尾。,状态转移图,0,1,0,q,1,q,2,1,0,q,t,0,1,1,q,0,例,3-10,构造,DFA,识别,0,，,1,上的语言，该语言的每个字符串,不包含,00,子串,(,语言允许,),0,0,0,1,q,t,q,1,q,0,q,2,1,0,1,1,或,0,0,0,1,q,t,q,1,q,0,1,1,构造,DFA,识别,0,，,1,上的语言，,该语言的每个字符串不包含,00,（,语言不允许,）,例,3-11,构造,DFA,识别,0,，,1,，,2,上的语言，,该语言的每个字符串代表的数字能整除,3,。,分析,如果一个十进制整数的所有位的,数字的和,能够整除,3,，那么，,这个十进制整数就能够整除,3,；,一个十进制整数除以,3,，余数只能是,1,、,2,和,0,；,将整数当作一个字符串，从左到右逐一地读入；,使用,3,个状态,分别代表已读入的数字的,和,除以,3,的,余数情况,：,(,即读入的整数对,3,的余数情况）,q,0,：,已,读入的整数除以,3,，,余数为,0,q,1,：,已,读入的整数除以,3,，,余数为,1,q,2,：,已,读入的整数除以,3,，,余数为,2,思考,已知,q,i,(i,=0,1,2),，,n=0,1,2,，,应该如何确定,j,？,q,i,q,j,n,扫描子串,w,后,处于某个状态,q,i,，,读入当前数字,状态转换情况为,q,0,在此状态读入,0,，引导,DFA,到达下一状态的输入串为,w0,w0,的各位数字和除以,3,，,余数为,0,。所以，,DFA,在,q,0,状态读入,0,，应该继续保持,q,0,状态；,q,0,在此状态读入,1,，引导,DFA,到达下一状态的输入串为,w1,，,w1,的各位数字和除以,3,，,余数为,1,。,所以，,DFA,在,q,0,状态读入,1,，应该到达,q,1,状态；,q,0,在此状态读入,2,，引导,DFA,到达下一状态的输入串为,w2,，,w2,的各位数字和除以,3,，,余数为,2,。,所以，,DFA,在,q,0,状态读入,2,，应该到达,q,2,状态；,存在的问题,接收的串包括以,0,开始,的数字串；,还能够接收,空串,思考,如何进行改进，使得,接收的串不能以,0,开始，,不能接收,空串,。,定义,3-9 set,集合,对于状态,q,，能将,DFA,从,q,0,转换到,q,状态的所有字符串的集合为：,set(q,),=w|w,*,*,(q,0,w)=q,则,有限状态自动机,DFA,接收的,语言可以定义为：,L(DFA)=,set(q,),其中：,q,F,按状态进行划分,对于,DFA,，,可以定义关系,R,若,x,y,*,，,qQ,则,xRy,当且仅当,xset(q),yset(q,),该关系是集合,*,上的一个,等价关系,，利用该关系，,可以将,*,划分为不多于,|Q|,个的,等价类,。,DFA,可以按照语言的特点给出字母表,*,的一个,划分,，这种划分相当于,*,上的一个等价分类。,DFA,每个,状态,对应着一个,等价类,利用一个,状态,去表示一个,等价类,是构造,DFA,的一条,有效思路,。,例,3-12,构造,DFA,识别,0,1,2,4,5,6,7,8,9,上的语言，,该语言的每个字符串代表的数字能整除,3,。,仍然,只使用,3,个状态分别代表已经读入的整数字的和除以,3,的不同的余数的情况：,状态与对应的等价类,q,0,：,余数为,0,的输入串的等价类,q,1,：,余数为,1,的输入串的等价类,q,2,：,余数为,2,的输入串的等价类,例,3-13,构造,DFA,识别,0,，,1,上的语言，该语言的每个字符串挡成,二进制数,时，,代表的数字能,整除,3,。,DFA,的每个状态对应一个等价类,利用一个状态去表示一个等价类,除以,3,的,余数只能为,0,、,1,和,2,q,0,：,余数为,0,的输入串的等价类；,q,1,：,余数为,1,的输入串的等价类；,q,2,：,余数为,2,的输入串的等价类；,不能接收空串，所以，,还需要一个开始状态,q,S,设,w,是当前读入的输入串；,q,S,：在开始状态,读入,0,时，,w=0,，进入状态,q,0,；,读入,1,时，,w=1,，进入状态,q,1,；,q,0,能引导,DFA,到达此状态的,w,除以,3,余数为,0,，因此,(w),10,=3n+0,q,0,在此状态读入,0,，引导,DFA,到达下一状态的输入串为,w0,，则,(w0),10,=2(3n+0)+0=32n+0,表明,w0,也属于,q,0,对应的等价类。所以，,DFA,在,q,0,状态读入,0,，应该继续保持,q,0,状态；,q,0,在此状态读入,1,，引导,DFA,到达下一状态的输入串为,w1,，则,(w1),10,=2(3n+0)+1=32n+1,表明,w1,属于,q,1,对应的等价类。所以，,DFA,在,q,0,状态读入,1,，应该到达,q,1,状态；,q,1,能引导,DFA,到达此状态的,w,除以,3,余数为,1,，因此,(w,),10,=3n+1,q,1,在此状态读入,0,，引导,DFA,到达下一状态的输入串为,w0,，则,(w0),10,=2(3n+1)+0=32n+2,表明,w0,属于,q,2,对应的等价类。所以，,DFA,在,q,1,状态读入,0,，应该到达,q,2,状态；,q,1,在此状态读入,1,，引导,DFA,到达下一状态的输入串为,w1,，则,(w1,),10,=2(3n+1)+1=32n+3,表明,w1,属于,q,0,对应的等价类。所以，,DFA,在,q,1,状态读入,1,，应该到达,q,0,状态；,q,2,能引导,DFA,到达此状态的,w,除以,3,余数为,2,，因此，,(w),10,=3n+2,q,2,在此状态读入,0,，引导,DFA,到达下一状态的输入串为,w0,，则,(w0),10,=2(3n+2)+0=32n+4,表明,w0,属于,q,1,对应的等价类。所以，,DFA,在,q,2,状态读入,0,，应该到达,q,1,状态；,q,2,在此状态读入,1,，引导自动机到达下一状态的输入串为,w1,，则,(w1,),10,=2(3n+2)+1=32n+5,表明,w1,属于,q,2,对应的等价类。所以，自动机在,q,2,状态读入,1,，继续保持,q,2,状态；,状态图,例,3-14,构造,DFA,，识别,0,，,1,上的语言，该语言的每个字符串为,二进制数,时，,代表的数字能被,5,整除。,分析：,对,5,的余数只能为,0,、,1,、,2,、,3,和,4,使用,5,个状态,分别代表已经读入的数字除以,5,的不同的余数的等价类：,q,i,：已经读入的数除以,5,，余数为,i,的输入串的等价类；,其中,i=0,1,2,3,4,不能接收空串，需要一个开始状态,q,S,例,3-15,构造,DFA,，识别,1,2,3,上的语言，该语言的每个字符串挡成,十进制数,时，,代表的数字能被,4,整除。,思考：,构造,DFA,，识别,0,，,1,2,，,3,，,4,，,5,，,6,，,7,，,8,，,9,上的语言，该语言的每个字符串挡成,十进制,数时，,代表的数字能整除,7,。,总结：,构造,DFA,，识别,=x,1,x,2,x,3,x,m,上的语言,该语言的每个字符串挡成,base,进制数,时,代表的数字能整除,N,。,或 对,N,的余数为,K,。,分析：,对,N,的,余数,只能为,0,、,1,、,2,、,3,、,和,N-1,。,使用,N,个状态,分别代表,已经读入的数,对,N,的不同的余数的等价类：,q,0,：余数为,0,的输入串的等价类；,该类数十进制为,N*n+0,q,1,：余数为,1,的输入串的等价类；该类数十进制为,N*n+1,q,2,：余数为,2,的输入串的等价类；该类数十进制为,N*n+2,q,N-1,：余数为,N-1,的输入串的等价类；该类数十进制为,N*n+N-1,注意,不能接收空串，,还需要一个,开始状态,q,S,q,S,读入,x,时，进入对应状态,q,i,本质,已知,q,i,(i,=0,，,1,，,2,，,N-1),x=x,1,x,2,x,3,x,m,应该如何确定,j,？,q,i,q,j,x,q,i,已经读如的数字为,w,，,对应余数为,i,的输入串的等价类；,该类数十进制为,N*,n+i,当前读入的字符为,x,；则,wx,表示的十进制数为,base*,（,N*,n+i,）,+x,=,N*base*,n+,base,*,i+x,该数对于,N,取余数就是,base*i+x,对于,N,的余数，,若该余数为,j,，,则相应的状态就应该从,q,i,变换为,q,j,其中,i=0,，,1,，,2,，,，,N-1,。,x,=,x,1,x,2,x,3,x,m,至多,=,0,1,，,，,base-1,例,3-16,构造,DFA,，识别,0,，,1,上的语言,L=,0,n,1,m,2,k,|n,m,k=1,该语言的串的特点是，,0,在最前面，,1,在中间，,2,在最后，,0,、,1,和,2,不能交叉,，顺序也,不能颠倒,。,0,、,1,和,2,的个数都至少为,1,个；,需要,4,个状态,：,q,0,：,开始状态,等待接收第,1,个,0,q,1,：,已经,接收第,1,个,0,，,负责,接收可能的多个,0,，,等待,接收第,1,个,1,；,q,2,：,已经接收第,1,个,1,，负责接收可能的多个,1,，等待接收第,1,个,2,；,q,3,：,已经接收第,1,个,2,，负责接收可能的多个,2,。,状态转移图,(,省略陷阱状态,),q,0,0,1,0,1,2,2,q,1,q,2,q,3,思考,1,补充陷阱状态及对应的状态函数。,思考,2,DFA,是否可以为,(,省略陷阱状态,),q,0,0,1,0,1,2,2,q,1,q,2,q,3,