第二章上下文无关文法.ppt

Click to edit Title Slide,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,*,*,第2章,上下文无关文法,研究内容,上下文无关文法概述,下推自动机,非上下文无关语言,2026/1/31 周六,1,上下文无关文法的应用,上下文无关文法的重要性如下,表达能力强大足于表示大多数程序设计语言语法,可以构造有效的分析算法以检验一个给定的字符串是否由某个上下文无关文法产生,上下文无关语言在实践中的重要意义,定义程序设计语言：例如,BNF,范式,描述文档格式：例如,XML,，,HTML,使语法分析概念形式化,简化程序设计语言的翻译：例如设计语法分析器,2026/1/31 周六,2,上下文无关文法的应用,语法分析程序,语法分析程序生成器,超文本标记语言,可扩展标记语言,2026/1/31 周六,3,文法的形式定义,文法,G,是一个四元组：,G=(V,N,V,T,P,Z),，,其中：,V,N,是非终结符的有穷集合，也称为语法单元、语法成分或语法范畴，可分解为若干非终结符或终结符,V,T,是终结符的有穷集合，是基本符号，不能再分解,V=V,N,V,T,称为字汇表,(,字母表,),，,V,N,V,T,=,。,Z,是开始符，,ZV,N,，,P,是规则式（产生式）有穷集合,规则式形如：,xy,，其中,xV,*,V,N,V,*,称为规则式的左部；,yV,*,称为右部。,2026/1/31 周六,4,文法的类型,Chomsky,将文法分为四种类型：,型文法（短语结构文法，可压缩的上下文有关文法），最一般的文法，对规则无限制,uw,uV,*,V,N,V,*,wV,*,（可为,）,相应的自动机是图灵机,型文法（上下文有关文法,不可压缩的上下文有关文法），对规则有些限制,xuyxwy,x,和,y,就是上下文，,x,yV,*,，,uV,*,V,N,wV,+,（不可为,），这些限制也可以写成：,uw,|,u|w,|,意为串的长度不可压缩,相应的自动机是线性界限自动机,2026/1/31 周六,5,文法的类型,型文法（上下文无关文法，简单短语结构文法），对规则的限制,Aw,AV,N,wV,*,（可为,）,型文法与字典定义形式相近（一个字用另一些字定义），与人们习惯一致。,相应的自动机是下推自动机，与,BNF,等价。左部均为非终结符,2026/1/31 周六,6,文法的类型,型文法（正规文法，正则文法），规则是线性的，其中,左线性：,ABa,Aa,右线性：,AaB,Aa,A,，,BV,N,aV,T,相应的自动机是有限自动机。在程序设计语言中，单词符号用型文法定义。,2026/1/31 周六,7,上下文无关文法概述,上下文无关文法是把变量转化为原语符号串的一组规则，即变量,变量或原语符号组成的串,上下文无关文法最早被用来描述自然语言的一些规则，在计算机语言学中，,Backus,范式,可以用来表示一种程序设计语言的各种规定，例如字符集、标识字符集、标识符以及各种语句的格式等,2026/1/31 周六,8,上下文无关文法概述,文法,G=(V，,，R，S),被称为是上下文无关文法或2型文法。如果对于,R,，,均有|,|,|，,并且,V,成立。,关键：对于,AV，,如果,A,P,，,则无论,A,出现在句型的任何位置，我们都可以将,A,替换成,，,而不考虑,A,的上下文。,L(G),叫做2型语言(,type 2 language),或者上下文无关语言(,context free language,CFL)。,2026/1/31 周六,9,上下文无关文法,(,例子,),构造上下文无关文法,G,，它所产生的语言为字母表,0,1,上所有回文全体，即,L(G)=w,0,1,*,|w=,w,R,G=(S,0,1;R,S),，其中,R,：,S,|1|0,；,S,OSO|1S1,分别构造如下三个语言的上下文无关文法,L,1,=a,n,b,n,|n,1,；,L,2,=a,n,b,n,c,m,d,m,|n,m,1,L,3,=a,n,b,m,c,m,d,n,|n,m,1,G,1,=(S,a,b;R,1,S),，其中,R,1,：,S,aSb|ab,G,2,=(S,A,B,a,b,c,d;R,2,S),，其中,R,2,：,S,AB,，,A,aAb|ab,，,BcBd|cd,G,2,=(S,A,a,b,c,d;R,3,S),，其中,R,2,：,S,aSd|aAd,，,A,bAc|bc,2026/1/31 周六,10,上下文无关文法的形式化定义,定义2.1,上下文无关文法是一个4元组,G=(V,R,S),V:,一个有穷集，称为变元集,:,一个有穷集，称为终结符集,，,(,V,=),R:,有穷规则集，,V,(V,)*,SV:,起始变元,文法,G,的语言可以表示为,L(G)=w,*|S*w,规则左边是单个变元符号，右边的所有符号属于集合,V,2026/1/31 周六,11,上下文无关文法的推导和派生,设,u,，,v,和,是由变元及终结符构成的字符串，,A,是文法的一条规则，称,uAv,生成,u,v,，记作,uAvu,v,。如果,u=v,，或者存在序列,u,1,，,u,2,，,，,u,k,，使得,uu,1,u,2,u,k,v,其中,k0,，则称,u,派生,v,，记作,u,*,v,。,该文法的语言是,*,|S,*,2026/1/31 周六,12,上下文无关文法的形式化定义,在描述一个文法时，通常只写出它的规则,出现在规则左边的符号都是变元，其余的符号都是终结符，按照惯例，起始变元是第一条规则左边的变元,2026/1/31 周六,13,上下文无关文法举例,例题,2.2,：考虑文法,G,3,:,例题,2.3,：考虑文法,G,4,及其生成字符串,a+a,*a,和,(,a+a,)*a,的语法分析树及其过程,编译程序把用程序设计语言编写的代码翻译成另一种更适合机器执行的代码,编译程序提取被编译代码的语义，这一个过程称为语法分析,2026/1/31 周六,14,上下文无关语言与高级程序语言,生成标识符的上下文无关文法,SSA|A|SD,Aa|b|c,w|x|y|z,|_,D,0|1|2|3|4|5|6|7|8|9,生成正整形常量的上下文无关文法,SA|BC,CCA|A,B|1|2|3|4|5|6|7|8|9,A0|B,2026/1/31 周六,15,上下文无关语言与高级程序语言,生成条件语句,if,then,和,if,then,else,的上下文无关文法,(,具有二义性,),Sif,C then S,Sif,C then S else S,Sa|b,Cp|q,If p then if q then a else b,S,if,C,then,S,p,if,C,then,S,else,S,q,a,b,S,if,C,then,S,p,if,C,then,S,else,S,q,a,b,2026/1/31 周六,16,上下文无关语言与高级程序语言,生成条件语句,if,then,和,if,then,else,的上下文无关文法,(,消除二义性,),SS1|S2,S1if C then S1 else S2|T,S2if C then S|if C then S1 else S2|T,Ta|b,Cp|q,If p then if q then a else b,S,if,C,then,S1,p,if,C,then,S1,else,S2,q,T,T,(,或,S2),a,b,2026/1/31 周六,17,形式语言与自然语言,上下文无关文法也可以描述自然语言（以英语为例）,SNP VP,NPDet,N|,Det,A N,AAdj,A|,Adj,VPV,be,PP,PPP,rep,NP,V,be,am,|is|are,Deta,|an|the,P,rep,on,|in|for|,V,play|go|.,N boy|girl|,Adjsmall,|big|high|.,The big red ball is on the table,的推导树,S,NP,V,be,PP,Adj,Det,A,N,the,A,P,rep,VP,red,is,Adj,big,ball,NP,on,Det,N,table,the,2026/1/31 周六,18,设计上下文无关文法,设计上下文无关文法比设计有穷自动机更加棘手,设计上下文无关的一些基本技巧：,首先，化繁为简，把一个,CFL,问题分解成几个简单的,CFL,问题,其次，利用正则，如果一个语言碰巧是正则的，则可先构造它的,DFA,，再构造其,CFG,再次，考察子串,最后，利用递归,2026/1/31 周六,19,设计上下文无关文法,将一台,DFA,转变成等价的,CFG,为,DFA,的每个状态,q,i,指定一个变元,R,i,，,如果,(,q,i,，,a)=,q,j,是,DFA,的一个转移，则把规则,R,i,aR,j,加入,CFG,如果,q,i,是,DFA,的接受状态，则把规则,R,i,加入,CFG,如果,q,0,是,DFA,的起始状态，则取,R,0,作为,CFG,的起始变元,2026/1/31 周六,20,基本的语法分析方法,对给定的上下文无关文法,G=(V,N,V,T,P,Z),及符号串,w,V,T,*,，语法分析就是判断串,w,是否是文法,G,产生的合法句子，即,S,*,w,是否成立？,对于计算机程序语言及其编写的程序而言，语法分析的任务就是判断程序中的各个句子是否合法？进一步判断整个程序是否合法？,2026/1/31 周六,21,基本的语法分析方法,基本的语法分析方法有两种：,自顶向下分析法：从文法的开始符号出发，能否找到一个最左推导序列导出,w,，即,S,+,w,，或者从根节点,S,开始，是否能向下构造一棵推导树产生串,w,自底向上分析法：从字符串,w,出发寻找一个归约序列，逐步对可归约串向上进行归约，直到文法的开始符号,S,2026/1/31 周六,22,歧义性概述,如果一个文法以不同的方式产生同一个字符串，则称文法歧义地产生这个字符串,如果一个文法歧义地产生某个字符串，则称这个文法是歧义的,2026/1/31 周六,23,歧义性概述,一个文法歧义地产生一个字符串的意思是：该字符串是两棵,不同的语法分析树,，而不是两种,不同的派生,，两种不同的派生可能仅仅是替换变元的次序不同，而不是整个结构的不同,对于文法,G,中的一个字符串,的派生，如果在每一步都是替换最左边剩下的变元，则称这个派生是,最左派生,2026/1/31 周六,24,歧义性例子,一个歧义文法,G,5,：,+|*|()|a,这个文法歧义地,产生,字符串,a+a,*a,EXPR,EXPR,EXPR,a,EXPR,EXPR,a,+,a,*,EXPR,EXPR,EXPR,a,EXPR,EXPR,a,+,a,*,2026/1/31 周六,25,歧义性的形式化描述,定义,2.4,：,如果字符串,在上下文法,G,中有两个或两个以上不同的最左派生，则称,G,歧义地产生字符串,，如果文法,G,歧义地产生某个字符串，则称,G,是歧义的。,固有歧义：,某些上下文无关语言只能用歧义文法产生，这样的语言称为,固有歧义的。,2026/1/31 周六,26,上下文无关歧义文法,G,2,一个歧义文法,G,2,：,|,|,|,a|the,boy|girl|flower,touches|likes|sees,with,2026/1/31 周六,27,歧义派生语法树,1,The girl touches the boy with the flower,在,G,2,文法下的语法分析树,1,：,The,girl,touches,the,boy,with,the,flower,2026/1/31 周六,28,歧义派生语法树,2,The girl touches the boy with the flower,在,G,2,文法下的语法分析树,2,The,girl,touches,the,boy,with,the,flower,2026/1/31 周六,29,上下文无关文法的化简,对一个上下文无关语言,L,，可以有多个上下文无关文法,G,，使得,L=L,（,G,），,其中可能有的文法包含一些对产生该语言没有作用的字符（变量和终结符）和产生式,无用字符,空产生式,单产生式,上下文无关文法化简的目的是在不降低文法生成句子能力的前提下，通过限制产生式的格式来降低文法分析算法的复杂度,乔姆斯基范式和格雷巴赫范式,2026/1/31 周六,30,无用字符,定义：,G=(V,R,S),是一个上下文无关文法，字符,XV,，如果存在,G,的一个推导,S,*,X,*,w,，其中,，,w,*,，则称字符,X,是文法,G,中的一个有用字符，否则称,X,为一个无用字符,上下文无关文法化简的任务之一就是要消去文法中出现的无用字符。一个字符是无用字符有两种情况：,对于一个变量,A,，如果不能从,A,中推导出终结符串,(,即不存在,w,*,，使得,A,*,w,),，则,A,是无用的,对于任意,A,V,，如果,A,不出现从初始符号,S,出现的任何句型中，则,A,是无用的,2026/1/31 周六,31,无用字符算法,算法,1,：消去文法中那些不能推导出终极符串的变量,输入：上下文无关文法,G=(V,R,S),输出：,G,中那些能推导出终极符串的变量集合,V,算法步骤：,Step1:V,0,=,Step2:V,N,=AV|,存在,w,*,使得,A,w,是,G,的一个产生式,Step3:While V,0,V,N,do Begin V,0,=V,0,V,N,；,V,N,=AV|,存在,(,V,N,),*,使得,A,是,G,的一个产生式,end,Step4:V,=V,N,2026/1/31 周六,32,无用字符算法,算法,2,：消去文法中不出现在句型中的变量和终极符,输入：上下文无关文法,G=(V,R,S),输出：可出现在,G,的句型中的变量集合,V,和可出现在,G,的句型中的终极符集,算法步骤：,Step1,：,V,=S,=,Step2,：,V,=,A,V,a,|,存在产生式,A,，使得,B,出现在,中,N,=,A,V,a,|,存在产生式,A,，使得,a,出现在,中,=,N,Step3:if V,N,-V,=,then output,V,and,else,Begin V,=V,N,V,;,goto,step2 End,2026/1/31 周六,33,无用字符,定理：每个非空的上下文无关语言都可以由一个没有无用字符的上下文无关文法产生,例子：上下文无关文法,G,1,=(S,A,B,a,R,1,S),，其中,R,1,：,S,AB|a,，,A,a,，故,L(G,1,)=a,由算法,1,，,B,是一个不能推导出终极符串的变量，故得,G,2,=(S,A,a,R,2,S),，其中,R,1,：,S,a,，,A,a,由算法,2,，,A,也不出现,G,2,的任何一个句型中，故得,G,3,=(S,a,R,3,S),，其中,R,1,：,S,a,2026/1/31 周六,34,空产生式,A,型的产生式称为空产生式。对于一个上下文无关文法,G,，如果,L(G),，那么,G,中的空产生式就是不必要的了,如果出现空产生式，则化简的任务之一就是从文法中消去那些空产生式,2026/1/31 周六,35,空产生式,(,反例,),例子：设文法,G,1,=(S,A,B,a,b,R,1,S),，其中,R,1,：,SAB,AaA|a,Bb,|,易知,L(G,1,)=a,n,b|n1a,n,|n1,。由于,L(G,1,),，对,G,1,化简的任务之一就是设法从,G,1,中删去空产生式。如果只是简单地删去,B,，则得到文法,G,2,=(S,A,B,a,b,R,2,S),，其中,R,2,：,SAB,AaA|a,Bb,，,易知,L(G,2,)=a,n,b|n1,。显然,L(G,1,),L(G,2,),，所以简单删去的方法是不行的,2026/1/31 周六,36,空产生式算法,从上下文无关文法,G=(V,R,S)(,L(G),中删去空产生式获得等价文法,G,的算法,Step1,：找出,G,中那些能够推导出空串,的变量集合,V,=A,V|A,*,Step2,：对每个,X,i,V,，对,G,中每个产生式,AX,1,X,i-1,X,i,X,i+1,X,n,(X,j,V,ji,),增加一个产生式,AX,1,X,i-1,X,i+1,X,n,Step2,：从,G,中删去所有空产生式,2026/1/31 周六,37,空产生式,(,例子,),对前述文法,G,1,=(S,A,B,a,b,R,1,S),，其中,R,1,：,SAB,AaA|a,Bb,|,易知,V,=AV|A,*,=B,，相关产生式有,SAB,，因此需要增加一个产生式,SA,，然后删去空产生式,B,，得到一个与,G,1,文法等价的不含空产生式的文法,G,3,=(S,A,B,a,b,R,3,S),，其中,R,3,：,SAB|A,AaA|a,Bb,易知,L(G,3,)=L(G,1,),2026/1/31 周六,38,空产生式,定理：每个不含空串的上下文无关语言都可以由一个不含空产生式的上下文无关文法产生,推论：设,G,是一个上下文无关文法，则,L(G)-,可以由一个不含空产生式的上下文无关文法产生,2026/1/31 周六,39,单产生式,对上下文无关文法,G=(V,R,S),，若,A,BV,，则,AB,型的产生式称为单产生式,单产生式在文法中出现是没有必要的，上下文无关文法化简的任务之一就是设法消去文法中出现的单产生式,单产生式的处理有两种情况：,2026/1/31 周六,40,单产生式的两种情况,单产生式的处理有两种情况：,情况,1,：,设,AB,是文法,G,的一个单产生式，如果,G,中不存在,A,*,1,A,2,型的推导，则在删去单产生式,AB,的同时，把各个产生式中出现的变量,B,都改成,A,，即可以得到一个没有单产生式,AB,且同,G,等价的文法,G,情况,2,：,设,AB,是文法,G,的一个单产生式，如果,G,中存在,A,*,1,A,2,型的推导，则在删去单产生式,AB,的同时，对,G,中的每个,B,产生式,B,，都添加一个,A-,产生式,A,，即可以得到一个没有单产生式,AB,且同,G,等价的文法,G,2026/1/31 周六,41,单产生式,(,例子,1),对文法,G,3,：,G,3,=(S,A,B,a,b,R,3,S),，其中,R,3,：,SAB|A,AaA|a,Bb,考虑单产生式,SA,，此处属于情况,1,。因此删除单产生式,SA,，并将其它产生式中,A,改为,S,，得到文法,G,4,，,G,4,=(S,B,a,b,R,4,S),，其中,R,4,：,SSB|aS|a,Bb,2026/1/31 周六,42,单产生式,(,例子,2),对文法,G,：,G=(,S,A,a,b,c,R,S,),，其中,R,3,：,SaS|A,AbA|c,易知,L(G)=a,n,b,m,c|n,m,0,。此中单产生式,SA,，但其中含有,AbA,，属于情况,2,。首先对应于,S-,产生式,SaS,，应该增加一个产生式,SaA,，其次对应于,A-,产生式,AbA,和,Ac,，分别增加两个产生式,SbA,和,Sc,，这样得到一个没有单产生式且等价于,G,的文法,G=(,S,A,a,b,c,R,S,),，其中,R,：,SaS|bA|c,AbA|c,2026/1/31 周六,43,单产生式,定理：设,L,是一个上下文无关语言，且,L,，则,L,可以由一个没有无用字符、没有空产生式、没有单产生式的上下文无关文法产生,2026/1/31 周六,44,乔姆斯基范式,定义2.5 称一个上下文无关文法,G=(V,，,，,R,，,S),为乔姆斯基范式，如果它的每一个规则具有如下形式,A,BC(,一分为二,),，或,A,a,(,终极字符,),其中，,AV and B,CVS,and a,此外允许规则,S,，其中,S,是起始变元,2026/1/31 周六,45,乔姆斯基范式,定理,2.6,：,任意上下文无关语言都可以用一个乔姆斯基范式的上下文无关文法产生,证明思路：,转换时分几个阶段把不符合要求的规则替换成等价的符合要求的规则,首先，添加一个新的起始变元，然后删除所有形如,A,的,规则，再删除所有形如,AB,的单一规则,在删除时，要对文法做适当的弥补，以确保仍然产生相同的语言,最后，把所有留下的规则转换成适当的形式,2026/1/31 周六,46,例子,2.7,2026/1/31 周六,47,例子,2.7,2026/1/31 周六,48,乔姆斯基范式,(,例子,),对于文法,G,1,=(S,A,B,a,b,R,1,S),，其中,R,1,：,SbA|aB,，,AbAA|aS|a,BaBB|bS|b,利用上述定理的方法，可以改造成,乔姆斯基范式,G,，其产生式集,R,：,S,C,a,A|C,a,B,，,C,a,a,，,C,b,b,，,AC,b,D,1,|C,a,S|a,，,D,1,AA,，,D,2,BB,，,BC,a,D,2,|C,b,S|b,2026/1/31 周六,49,格雷巴赫范式,对于一个不含有空串,的上下文无关语言,L,，格雷巴赫范式要求产生,L,的上下文无关文法,G=(V,R,S),的每个产生式都具有,Aa,，,a,，,V,*,的形式,2026/1/31 周六,50,格雷巴赫范式,引理,1,：,设,G=(V,R,S),是一个上下文无关文法，其中,A,1,B,2,，,B,V,，,1,B,2,(,V,),*,是,G,中的产生式，而,B,1,|,2,|,|,r,，,i,(,V,),*,是,G,中的全部,B-,产生式。令,G,1,=(V,R,1,S),，其中,R,1,是从,R,中删去产生式,A,1,B,2,，而添上,r,个产生式,A,1,1,2,|,1,2,2,|,|,1,r,2,|,而得到，则,L(G,1,)=L(G,2,),2026/1/31 周六,51,格雷巴赫范式,引理,2,：,设,G=(V,R,S),是一个上下文无关文法，其中,AA,1,|A,2,|,|A,r,是,G,中全部以,A,为右端首字符的,A-,产生式，,G,中其余的,A-,产生式为,A,1,|,2,|,|,s,。令,G,1,=(VB,R,1,S),，其中,R,1,是把,R,中全部,A-,产生式用下面两组产生式替换而得到的产生式集，则,L(G,1,)=L(G,2,),1,）,A,j,|,j,B,，,j=1,2,s,2,）,B,i,|,i,B,，,i=1,2,r,2026/1/31 周六,52,格雷巴赫范式,定理,1,：,任何不含空串,的上下文无关语言,L,都可以由这些的一种文法,G=(V,R,S),产生，其中,G,中的产生式都有,Aa,，,a,，,V,*,的形式,把一个上下文无关文法改造成格雷巴赫范式的工作是非常复杂的，并不是多项式时间复杂性的。利用上下文无关的格雷巴赫范式，可以对上下文无关文法的一些性质从理论上证明提供方便,2026/1/31 周六,53,下推自动机,下推自动机,PDA,：,描述,CFL（,上下文无关语言）的设备,PDA：,在能力上与上下文无关文法等价，在证明一个语言是上下文无关的时候，或者给出生成它的上下文无关文法，或者给出识别它的,PDA,PDA：“,硬件,”,方面增加了栈（先进后出），使其能识别某些非正则语言,PDA：,能够向栈中写入一个符号（下推），也可以从栈中读取（删除，弹出）一个符号，其对栈的访问遵循先进后出原则,2026/1/31 周六,54,PDA,结构示意图,a,1,a,2,a,i,a,n,有限状态,控制器,下推栈,z,0,z,1,下推自动机的结构示意图,2026/1/31 周六,55,PDA,基本结构,PDA,应该含有三个基本结构,存放输入符号串的输入带,存放文法符号的栈,有穷状态控制器,PDA,的动作,在有穷状态控制器的控制下根据它的当前状态、栈顶符号、以及输入符号作出相应的动作，在有的时候，不需要考虑输入符号,2026/1/31 周六,56,例子,输入,w=00100100111100101,internal state,set,Q,x,y,y,z,x,stack,当读完,W,且进入终止态，则接受,w,栈用来作简单记忆历史对比，,只是栈顶元素可见，能力有限，且不灵活,2026/1/31 周六,57,PDA,可以是非确定型的，确定型,PDA,与非确定型,PDA,在语言识别能力上不相同，非确定型,PDA,能识别确定型,PDA,不能识别的一些语言，这与（非）确定型有穷自动机不相同。,非确定型下,PDA,等价于上下文无关文法。,PDA,类型,2026/1/31 周六,58,下推自动机,M,被定义为七元组,(Q,q,0,Z,0,F,),(,以终止状态接受语言,),，或者,(Q,q,0,Z,0,),(,以空栈方式接受语言,),，这里,Q,和,F,都是有穷集,Q,是状态集,是输入字母表,栈字符表,q,0,Q,是起始状态,FQ,是接受状态,(,终止状态,),集,是状态转移函数,Z,0,是初始栈顶符号,：,Q,P(Q,*,),=,=,PDA,的形式化定义,2026/1/31 周六,59,(q,a,Z,)=(p,1,r,1,),(p,2,r,2,),(,p,m,r,m,),表示,M,在状态,q，,栈顶符号为,Z,时，读入字符,a，,对于,i=1,2,m，,可以选择地将状态变成,p,i,，,并将栈顶符号,Z,弹出，将,i,中的符号压入栈，然后将读头向右移动一个带方格而指向输入字符串的下一个字符,PDA,的形式化定义,2026/1/31 周六,60,(q,Z,)=(p,1,r,1,),(p,2,r,2,),(,p,m,r,m,),表示,M,进行一次,-,移动(空移动)，即,M,在状态,q，,栈顶符号为,Z,时，无论输入符号是什么，,对于,i=1,2,m，,可以选择地将状态变成,p,i,，,并将栈顶符号,Z,弹出，,将,r,i,中的符号从右到左依次压入栈，读头,不移动,PDA,的形式化定义,2026/1/31 周六,61,下推自动机的瞬像是一个三元组(,q,w,r,),，其中,q,表示当前状态，,w,表示输入串中待扫描的子串，,r,表示下推栈中当前的内容,(,栈字符串,),若,(p,),(q,a,Z,),，则有一步瞬像推导,(,q,aw,Zr,)(,p,w,r,),。若用,*,表示下推自动机的若干步推导，则,以空栈方式接受语言的的下推自动机,M,所接受的语言为,N(M)=w,*,|,(q,0,w,Z,0,),*,(p,),以终止状态接受语言的的下推自动机,M,所接受的语言为,N(M)=w,*,|,(q,0,w,Z,0,),*,(p,r),p,F,PDA,的形式化定义,2026/1/31 周六,62,一台下推自动机,M=(Q,q,0,F,),的计算过程如下：,它接受输入,，如果能够把,写成,=,1,2,m,，这里,i,，并且存在序列,r,0,r,1,r,m,Q,和字符串序列,s,0,，,s,1,s,m,*,，满足下面三个条件，字符串,s,i,是,M,在计算的接受分支中的栈内容序列,r,0,=q,0,，,且,s,0,=,，表示,M,从初始状态和空栈开始,对于,i=0,1,m-1,，有,(r,i+1,b),(,r,i,i+1,a,),，其中,s,i,=at,，,s,i+1,=,bt,，,a,，,b,，和,t,*,r,m,F,PDA,计算过程,2026/1/31 周六,63,定理,1,：,若语言,L,被一个以终止状态方式接受语言的,PDA M,2,接受，当且仅当,L,被一个以空栈方式接受语言的,PDA M,1,接受,PDA,的等价性,2026/1/31 周六,64,一个例子,例2.9,:PDA,对语言,0,n,1,n,n0,的识别,读取输入串中的符号，每读一个,0,，把它推入栈,一旦看见,1,之后，每读一个,1,，把一个,0,弹出栈,当栈中的,0,被清空时恰好读完输入串，则接受,如果还有,1,没有读完的时候栈已空，或栈未空输入串已经读完，或,0,出现在,1,之后，则拒绝。,2026/1/31 周六,65,一个例子,例2.9,:PDA,识别语言,L=0,n,1,n,|n,0,的,转移函数,(q,1,)=(q,2,$),(q,2,0,)=(q,2,0),(q,2,1,0)=(q,3,),(q,3,1,0)=(q,3,),(q,3,$)=(q,4,),2026/1/31 周六,66,例2.9,:L=0,n,1,n,|n,0,背景：检查左右括号,(0,1),是否配对,PDA,首先把,“,$0,n,”,推入栈.,$栈底符号，表示后来压入栈的存款用完了,然后，当读到,“,1,n,”,0,被弹出.,栈顶对比，左右括号配对，则同归于尽,最后,如果,“,$,”,留在栈顶,，,则接受,q,1,q,3,q,2,q,4,$,$,1,0,1,0,0,0,一个例子,2026/1/31 周六,67,一个记号,(q,1,a,b)=(q,2,c),：,表示当状态,q,1,下，机器从输入中读到,a,，并且栈顶符号,b,时，就用符号,c,替换符号,b,，并转移到状态,q2,。记为：,(q,1,a,b)(q,2,c),，或写为,a,bc,a,b,c,中任何一个都可以为,当,a,是,时，则机器不读入任何符号，用符号,c,代替堆栈顶的,b,，并从状态,q1,转移到,q,2,当,b,是,时，则机器读入符号,a,，不从栈顶弹出任何符号，并压入符号,c,，并从状态,q1,转移到,q2,当,c,是,时，则机器读入符号,a,，从栈顶弹出符号,b,，不压入任何符号，并从状态,q,1,转移到,q,2,2026/1/31 周六,68,PDA,状态图描述,用“,a,b,c,”,表示当机器从输入中读,a,时可用,c,替换栈顶的符号,b,若,a,是,，则机器作这个转移，而不读取输入中的任何符号。,若,b,是,，则机器作这个转移，而不读栈中的任何符号，也不从栈中弹出任何符号。若,c,是,，则不在栈中写任何符号。,q,1,读,，栈顶,变,箱底钱,q,1,q,3,q,2,q,4,$,$,1,0,1,0,0,0,弹出压箱钱，栈空,在,q,2,遇,1,，弹出,0,兑消,q,3,遇右括号,1,，弹出,0,，,10,兑消,q2,遇左括号,0,，压,0,栈入栈,2026/1/31 周六,69,q,1,q,3,q,2,q,4,$,$,1,0,1,0,0,0,w=000111,接受,w=000111,（,状态；堆栈）的变化过程：,(q,1,;,),(q,2,;,$,),(q,2,;0,$,),(q,2,;00,$,),(q,2,;000,$,),(q,3,;00,$,),(q,3,;0,$,),(q,3,;,$,),(q,4,;,),终态,q,4,是个接受态,状态,栈内值,2026/1/31 周六,70,q,1,q,3,q,2,q,4,$,$,1,0,1,0,0,0,w=0101,拒绝,w=0101,（,状态；堆栈）的变化过程,：,(q,1,;,),(q,2,;,$,),(q,2,;0,$,),(q,3,;,$,),(q,4,;,),虽然具有输入的部分子串,“,01,”,，但找不到整个字符串的接受路径,理解为用括号配对比较直观,状态,栈内值,2026/1/31 周六,71,问题：,设计一个下推自动机接受语言,L,1,=wcw,R,|w0,1,*,解题思路：,L,1,中串是一个回文结构，中间以字母,c,分界,读取输入串中的,0,或,1,，把它推入栈，状态不变,一旦看见字母,c,之后，进入一个新状态,在新状态下，当输入字母与栈顶符号相同，出栈，状态不变，直到输入结束与栈空同时出现，则接受,如果如果输入字母与栈顶符号不相同，则拒绝,一个例子,2026/1/31 周六,72,问题：,设计一个下推自动机接受语言,L,1,=wcw,R,|w0,1,*,解题：,接受,L,1,的下推自动机表示为：,M,1,=(q,1,q,2,0,1,c R,0,1,q,1,R,),其中,为,(q,1,0,R)=(q,1,0R);(q,1,1,R)=(q,1,1R);,(q,1,c,R)=(q,2,R);(q,1,0,0)=(q,1,00);,(q,1,1,0)=(q,1,10);(q,1,c,0)=(q,2,0);,(q,1,0,1)=(q,1,01);(q,1,1,1)=(q,1,11);,(q,1,c,1)=(q,2,1);(q,2,1,1)=(q,2,);,(q,2,0,0)=(q,2,);(q,2,R)=(q,2,);,例如输入串,x=101c101,，其推导过程：,(q,1,101c101,R)(q,1,01c101,1R)(q,1,1c101,01R)(q,1,c101,101R)(q,2,101,101R)(q,2,01,01R)(q,2,1,1R)(q,2,R)(q,2,),一个例子,2026/1/31 周六,73,问题：,设计一个接受语言,L,2,=ww,R,|w0,1,*,的下推自动机,解题：,接受,L,2,的下推自动机表示为：,M,2,=(q,1,q,2,0,1 R,0,1,q,1,R,),这是空栈方式接受语言。其中,为,(q,1,0,R)=(q,1,0R);(q,1,1,R)=(q,1,1R);,(q,1,0,0)=(q,1,00),(q,2,);(q,1,1,0)=(q,1,10);,(q,1,1,1)=(q,1,11),(q,2,);(q,1,0,1)=(q,1,01);,(q,2,1,1)=(q,2,);(q,2,0,0)=(q,2,);,(q,2,R)=(q,2,);(q,1,R)=(q,2,);,一个例子,2026/1/31 周六,74,例如输入串,x=001100,，其推导过程：,一个例子,(q,1,001100,R),(q,1,01100,0R),(q,1,100,100R),(q,1,1100,00R),(q,2,1100,R),(q,2,001100,),(q,2,00,00R),(q,1,00,1100R),(q,2,0,0R),(q,2,R),(q,2,),(q,2,1100,),(q,1,0,01100R),(q,1,001100R),(q,2,1100R),2026/1/31 周六,75,问题：,设计一个接受语言,L,2,=ww,R,|w0,1,*,的下推自动机,解题：,接受,L,2,的下推自动机表示为：,M,2,=(q,0,q,1,q,2,q,f,0,1,X,0,R,0,1,0,q,0,X,0,q,f,),这是终止状态接受语言。其中,0,为,0,(q,0,X,0,)=(q,0,RX,0,),0,(q,1,0,R)=(q,1,0R);,0,(q,1,1,R)=(q,1,1R),0,(q,1,0,0)=(q,1,00),(q,2,);,0,(q,1,1,0)=(q,1,10),0,(q,1,1,1)=(q,1,11),(q,2,);,0,(q,1,0,1)=(q,1,01),0,(q,2,1,1)=(q,2,);,0,(q,2,0,0)=(q,2,),0,(q,2,R)=(q,2,);,0,(q,1,R)=(q,2,),0,(q,1,X,0,)=(q,f,X,0,);,0,(q,2,X,0,)=(q,f,X,0,),一个例子,2026/1/31 周六,76,计算过程,一个例子,(q,1,001100,RX,0,),(q,1,01100,0RX,0,),(q,1,100,100RX,0,),(q,1,1100,00RX,0,),(q,2,1100,RX,0,),(q,2,001100,X,0,),(q,2,00,00RX,0,),(q,1,00,1100RX,0,),(q,2,0,0RX,0,),(q,2,RX,0,),(q,2,X,0,),(q,f,1100,X,0,),(q,1,0,01100RX,0,),(q,1,