上下文无关文法.ppt

2023/10/8,1,第2章 上下文无关文法,研究内容上下文无关文法概述下推自动机非上下文无关语言,2023/10/8,2,上下文无关文法的应用,上下文无关文法的重要性如下表达能力强大足于表示大多数程序设计语言语法可以构造有效的分析算法以检验一个给定的字符串是否由某个上下文无关文法产生上下文无关语言在实践中的重要意义定义程序设计语言：例如BNF范式描述文档格式：例如XML，HTML使语法分析概念形式化简化程序设计语言的翻译：例如设计语法分析器,2023/10/8,3,上下文无关文法的应用,语法分析程序语法分析程序生成器超文本标记语言可扩展标记语言,2023/10/8,4,文法的形式定义,文法G是一个四元组：G=(VN,VT,P,Z)，其中：VN是非终结符的有穷集合，也称为语法单元、语法成分或语法范畴，可分解为若干非终结符或终结符VT是终结符的有穷集合，是基本符号，不能再分解V=VNVT称为字汇表(字母表)，VNVT=。Z是开始符，ZVN，P是规则式（产生式）有穷集合规则式形如：xy，其中xV*VNV*,称为规则式的左部；yV*称为右部。,2023/10/8,5,文法的类型,Chomsky将文法分为四种类型：型文法（短语结构文法，可压缩的上下文有关文法），最一般的文法，对规则无限制uw uV*VNV*wV*（可为）相应的自动机是图灵机型文法（上下文有关文法,不可压缩的上下文有关文法），对规则有些限制xuyxwy x和y就是上下文，x,yV*，uV*VN,wV+（不可为），这些限制也可以写成：uw|u|w|意为串的长度不可压缩相应的自动机是线性界限自动机,2023/10/8,6,文法的类型,型文法（上下文无关文法，简单短语结构文法），对规则的限制Aw AVN wV*（可为）型文法与字典定义形式相近（一个字用另一些字定义），与人们习惯一致。相应的自动机是下推自动机，与BNF等价。左部均为非终结符,2023/10/8,7,文法的类型,型文法（正规文法，正则文法），规则是线性的，其中左线性：ABa Aa右线性：AaB AaA，BVN,aVT相应的自动机是有限自动机。在程序设计语言中，单词符号用型文法定义。,2023/10/8,8,上下文无关文法概述,上下文无关文法是把变量转化为原语符号串的一组规则，即变量变量或原语符号组成的串上下文无关文法最早被用来描述自然语言的一些规则，在计算机语言学中，Backus范式可以用来表示一种程序设计语言的各种规定，例如字符集、标识字符集、标识符以及各种语句的格式等,2023/10/8,9,上下文无关文法概述,文法G=(V，R，S)被称为是上下文无关文法或2型文法。如果对于R，均有|，并且V成立。关键：对于AV，如果AP，则无论A出现在句型的任何位置，我们都可以将A替换成，而不考虑A的上下文。L(G)叫做2型语言(type 2 language)或者上下文无关语言(context free language,CFL)。,2023/10/8,10,上下文无关文法(例子),构造上下文无关文法G，它所产生的语言为字母表0,1上所有回文全体，即L(G)=w0,1*|w=wRG=(S,0,1;R,S)，其中R：S|1|0；SOSO|1S1 分别构造如下三个语言的上下文无关文法L1=anbn|n1；L2=anbncmdm|n,m1L3=anbmcmdn|n,m1G1=(S,a,b;R1,S)，其中R1：SaSb|abG2=(S,A,B,a,b,c,d;R2,S)，其中R2：SAB，AaAb|ab，BcBd|cdG2=(S,A,a,b,c,d;R3,S)，其中R2：SaSd|aAd，AbAc|bc,2023/10/8,11,上下文无关文法的形式化定义,定义2.1 上下文无关文法是一个4元组G=(V,R,S)V:一个有穷集，称为变元集:一个有穷集，称为终结符集，(V=)R:有穷规则集，V(V)*SV:起始变元文法G的语言可以表示为 L(G)=w*|S*w规则左边是单个变元符号，右边的所有符号属于集合V,2023/10/8,12,上下文无关文法的推导和派生,设u，v和是由变元及终结符构成的字符串，A是文法的一条规则，称uAv生成uv，记作uAvuv。如果u=v，或者存在序列u1，u2，uk，使得uu1u2ukv其中k0，则称u派生v，记作u*v。该文法的语言是*|S*,2023/10/8,13,上下文无关文法的形式化定义,在描述一个文法时，通常只写出它的规则出现在规则左边的符号都是变元，其余的符号都是终结符，按照惯例，起始变元是第一条规则左边的变元,2023/10/8,14,上下文无关文法举例,例题2.2：考虑文法G3:例题2.3：考虑文法G4及其生成字符串a+a*a和(a+a)*a的语法分析树及其过程编译程序把用程序设计语言编写的代码翻译成另一种更适合机器执行的代码编译程序提取被编译代码的语义，这一个过程称为语法分析,2023/10/8,15,上下文无关语言与高级程序语言,生成标识符的上下文无关文法 SSA|A|SD Aa|b|cw|x|y|z|_ D0|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,2023/10/8,16,上下文无关语言与高级程序语言,生成条件语句ifthen和ifthenelse的上下文无关文法(具有二义性)Sif C then S Sif C then S else S Sa|b Cp|qIf p then if q then a else b,2023/10/8,17,上下文无关语言与高级程序语言,生成条件语句ifthen和ifthenelse的上下文无关文法(消除二义性)SS1|S2 S1if C then S1 else S2|T S2if C then S|if C then S1 else S2|T Ta|b Cp|qIf p then if q then a else b,2023/10/8,18,形式语言与自然语言,上下文无关文法也可以描述自然语言（以英语为例）SNP VP NPDet N|Det A N AAdj A|Adj VPVbe PP PPPrep NP Vbeam|is|are Deta|an|the Prepon|in|for|V play|go|.N boy|girl|Adjsmall|big|high|.The big red ball is on the table的推导树,2023/10/8,19,设计上下文无关文法,设计上下文无关文法比设计有穷自动机更加棘手设计上下文无关的一些基本技巧：首先，化繁为简，把一个CFL问题分解成几个简单的CFL问题其次，利用正则，如果一个语言碰巧是正则的，则可先构造它的DFA，再构造其CFG再次，考察子串最后，利用递归,2023/10/8,20,设计上下文无关文法,将一台DFA转变成等价的CFG为DFA的每个状态qi指定一个变元Ri，如果(qi，a)=qj是DFA的一个转移，则把规则RiaRj加入CFG如果qi是DFA的接受状态，则把规则Ri加入CFG如果q0是DFA的起始状态，则取R0作为CFG的起始变元,2023/10/8,21,基本的语法分析方法,对给定的上下文无关文法G=(VN,VT,P,Z)及符号串wVT*，语法分析就是判断串w是否是文法G产生的合法句子，即S*w是否成立？对于计算机程序语言及其编写的程序而言，语法分析的任务就是判断程序中的各个句子是否合法？进一步判断整个程序是否合法？,2023/10/8,22,基本的语法分析方法,基本的语法分析方法有两种：自顶向下分析法：从文法的开始符号出发，能否找到一个最左推导序列导出w，即S+w，或者从根节点S开始，是否能向下构造一棵推导树产生串w自底向上分析法：从字符串w出发寻找一个归约序列，逐步对可归约串向上进行归约，直到文法的开始符号S,2023/10/8,23,歧义性概述,如果一个文法以不同的方式产生同一个字符串，则称文法歧义地产生这个字符串如果一个文法歧义地产生某个字符串，则称这个文法是歧义的,2023/10/8,24,歧义性概述,一个文法歧义地产生一个字符串的意思是：该字符串是两棵不同的语法分析树，而不是两种不同的派生，两种不同的派生可能仅仅是替换变元的次序不同，而不是整个结构的不同对于文法G中的一个字符串的派生，如果在每一步都是替换最左边剩下的变元，则称这个派生是最左派生,2023/10/8,25,歧义性例子,一个歧义文法G5：+|*|()|a这个文法歧义地产生字符串a+a*a,2023/10/8,26,歧义性的形式化描述,定义2.4：如果字符串在上下文法G中有两个或两个以上不同的最左派生，则称G歧义地产生字符串，如果文法G歧义地产生某个字符串，则称G是歧义的。固有歧义：某些上下文无关语言只能用歧义文法产生，这样的语言称为固有歧义的。,2023/10/8,27,上下文无关歧义文法G2,一个歧义文法G2：|a|theboy|girl|flowertouches|likes|seeswith,2023/10/8,28,歧义派生语法树1,The girl touches the boy with the flower在G2文法下的语法分析树1：,2023/10/8,29,歧义派生语法树2,The girl touches the boy with the flower在G2文法下的语法分析树2,2023/10/8,30,上下文无关文法的化简,对一个上下文无关语言L，可以有多个上下文无关文法G，使得L=L（G），其中可能有的文法包含一些对产生该语言没有作用的字符（变量和终结符）和产生式无用字符空产生式单产生式上下文无关文法化简的目的是在不降低文法生成句子能力的前提下，通过限制产生式的格式来降低文法分析算法的复杂度乔姆斯基范式和格雷巴赫范式,2023/10/8,31,无用字符,定义：G=(V,R,S)是一个上下文无关文法，字符XV，如果存在G的一个推导S*X*w，其中,，w*，则称字符X是文法G中的一个有用字符，否则称X为一个无用字符上下文无关文法化简的任务之一就是要消去文法中出现的无用字符。一个字符是无用字符有两种情况：对于一个变量A，如果不能从A中推导出终结符串(即不存在w*，使得A*w)，则A是无用的对于任意AV，如果A不出现从初始符号S出现的任何句型中，则A是无用的,2023/10/8,32,无用字符算法,算法1：消去文法中那些不能推导出终极符串的变量输入：上下文无关文法G=(V,R,S)输出：G中那些能推导出终极符串的变量集合V算法步骤：Step1:V0=Step2:VN=AV|存在w*,使得Aw是G的一个产生式Step3:While V0VN do Begin V0=V0VN；VN=AV|存在(VN)*,使得A是G的一个产生式 endStep4:V=VN,2023/10/8,33,无用字符算法,算法2：消去文法中不出现在句型中的变量和终极符输入：上下文无关文法G=(V,R,S)输出：可出现在G的句型中的变量集合V和可出现在G的句型中的终极符集算法步骤：Step1：V=S,=Step2：V=AVa|存在产生式A，使得B出现在中N=AVa|存在产生式A，使得a出现在中=NStep3:if VN-V=then output V and else Begin V=VNV;goto step2 End,2023/10/8,34,无用字符,定理：每个非空的上下文无关语言都可以由一个没有无用字符的上下文无关文法产生例子：上下文无关文法G1=(S,A,B,a,R1,S)，其中R1：SAB|a，Aa，故L(G1)=a由算法1，B是一个不能推导出终极符串的变量，故得G2=(S,A,a,R2,S)，其中R1：Sa，Aa由算法2，A也不出现G2的任何一个句型中，故得G3=(S,a,R3,S)，其中R1：Sa,2023/10/8,35,空产生式,A型的产生式称为空产生式。对于一个上下文无关文法G，如果L(G)，那么G中的空产生式就是不必要的了如果出现空产生式，则化简的任务之一就是从文法中消去那些空产生式,2023/10/8,36,空产生式(反例),例子：设文法 G1=(S,A,B,a,b,R1,S)，其中R1：SAB,AaA|a,Bb|易知L(G1)=anb|n1an|n1。由于L(G1)，对G1化简的任务之一就是设法从G1中删去空产生式。如果只是简单地删去B，则得到文法 G2=(S,A,B,a,b,R2,S)，其中R2：SAB,AaA|a,Bb，易知L(G2)=anb|n1。显然L(G1)L(G2)，所以简单删去的方法是不行的,2023/10/8,37,空产生式算法,从上下文无关文法G=(V,R,S)(L(G)中删去空产生式获得等价文法G的算法Step1：找出G中那些能够推导出空串的变量集合V=AV|A*Step2：对每个XiV，对G中每个产生式AX1Xi-1XiXi+1Xn,(XjV,ji)增加一个产生式AX1Xi-1Xi+1XnStep2：从G中删去所有空产生式,2023/10/8,38,空产生式(例子),对前述文法 G1=(S,A,B,a,b,R1,S)，其中R1：SAB,AaA|a,Bb|易知V=AV|A*=B，相关产生式有SAB，因此需要增加一个产生式SA，然后删去空产生式B，得到一个与G1文法等价的不含空产生式的文法G3=(S,A,B,a,b,R3,S)，其中R3：SAB|A,AaA|a,Bb 易知L(G3)=L(G1),2023/10/8,39,空产生式,定理：每个不含空串的上下文无关语言都可以由一个不含空产生式的上下文无关文法产生推论：设G是一个上下文无关文法，则L(G)-可以由一个不含空产生式的上下文无关文法产生,2023/10/8,40,单产生式,对上下文无关文法G=(V,R,S)，若A,BV，则AB型的产生式称为单产生式单产生式在文法中出现是没有必要的，上下文无关文法化简的任务之一就是设法消去文法中出现的单产生式单产生式的处理有两种情况：,2023/10/8,41,单产生式的两种情况,单产生式的处理有两种情况：情况1：设AB是文法G的一个单产生式，如果G中不存在A*1A2型的推导，则在删去单产生式AB的同时，把各个产生式中出现的变量B都改成A，即可以得到一个没有单产生式AB且同G等价的文法G情况2：设AB是文法G的一个单产生式，如果G中存在A*1A2型的推导，则在删去单产生式AB的同时，对G中的每个B产生式B，都添加一个A-产生式A，即可以得到一个没有单产生式AB且同G等价的文法G,2023/10/8,42,单产生式(例子1),对文法G3：G3=(S,A,B,a,b,R3,S)，其中R3：SAB|A,AaA|a,Bb考虑单产生式SA，此处属于情况1。因此删除单产生式SA，并将其它产生式中A改为S，得到文法G4，G4=(S,B,a,b,R4,S)，其中R4：SSB|aS|a,Bb,2023/10/8,43,单产生式(例子2),对文法G：G=(S,A,a,b,c,R,S)，其中R3：SaS|A,AbA|c易知L(G)=anbmc|n,m0。此中单产生式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,2023/10/8,44,单产生式,定理：设L是一个上下文无关语言，且L，则L可以由一个没有无用字符、没有空产生式、没有单产生式的上下文无关文法产生,2023/10/8,45,乔姆斯基范式,定义2.5 称一个上下文无关文法G=(V，R，S)为乔姆斯基范式，如果它的每一个规则具有如下形式ABC(一分为二)，或Aa(终极字符)其中，AV and B,CVS,and a此外允许规则S，其中S是起始变元,2023/10/8,46,乔姆斯基范式,定理2.6：任意上下文无关语言都可以用一个乔姆斯基范式的上下文无关文法产生证明思路：转换时分几个阶段把不符合要求的规则替换成等价的符合要求的规则首先，添加一个新的起始变元，然后删除所有形如A的规则，再删除所有形如AB的单一规则在删除时，要对文法做适当的弥补，以确保仍然产生相同的语言最后，把所有留下的规则转换成适当的形式,2023/10/8,47,例子2.7,2023/10/8,48,例子2.7,2023/10/8,49,乔姆斯基范式(例子),对于文法G1=(S,A,B,a,b,R1,S)，其中R1：SbA|aB，AbAA|aS|a,BaBB|bS|b利用上述定理的方法，可以改造成乔姆斯基范式G，其产生式集R：SCaA|CaB，Caa，Cbb，ACbD1|CaS|a，D1AA，D2BB，BCaD2|CbS|b,2023/10/8,50,格雷巴赫范式,对于一个不含有空串的上下文无关语言L，格雷巴赫范式要求产生L的上下文无关文法G=(V,R,S)的每个产生式都具有Aa，a，V*的形式,2023/10/8,51,格雷巴赫范式,引理1：设G=(V,R,S)是一个上下文无关文法，其中A1B2，BV，1B2(V)*是G中的产生式，而B1|2|r，i(V)*是G中的全部B-产生式。令G1=(V,R1,S)，其中R1是从R中删去产生式A1B2，而添上r个产生式A112|122|1 r2|而得到，则L(G1)=L(G2),2023/10/8,52,格雷巴赫范式,引理2：设G=(V,R,S)是一个上下文无关文法，其中AA1|A2|Ar是G中全部以A为右端首字符的A-产生式，G中其余的A-产生式为A1|2|s。令G1=(VB,R1,S)，其中R1是把R中全部A-产生式用下面两组产生式替换而得到的产生式集，则L(G1)=L(G2)1）Aj|jB，j=1,2,s2）Bi|iB，i=1,2,r,2023/10/8,53,格雷巴赫范式,定理1：任何不含空串的上下文无关语言L都可以由这些的一种文法G=(V,R,S)产生，其中G中的产生式都有Aa，a，V*的形式把一个上下文无关文法改造成格雷巴赫范式的工作是非常复杂的，并不是多项式时间复杂性的。利用上下文无关的格雷巴赫范式，可以对上下文无关文法的一些性质从理论上证明提供方便,2023/10/8,54,下推自动机,下推自动机PDA：描述CFL（上下文无关语言）的设备PDA：在能力上与上下文无关文法等价，在证明一个语言是上下文无关的时候，或者给出生成它的上下文无关文法，或者给出识别它的PDAPDA：“硬件”方面增加了栈（先进后出），使其能识别某些非正则语言PDA：能够向栈中写入一个符号（下推），也可以从栈中读取（删除，弹出）一个符号，其对栈的访问遵循先进后出原则,2023/10/8,55,PDA结构示意图,2023/10/8,56,PDA基本结构,PDA应该含有三个基本结构存放输入符号串的输入带存放文法符号的栈有穷状态控制器PDA的动作在有穷状态控制器的控制下根据它的当前状态、栈顶符号、以及输入符号作出相应的动作，在有的时候，不需要考虑输入符号,2023/10/8,57,例子,输入,internal state set Q,xyyzx,stack,当读完W且进入终止态，则接受w,栈用来作简单记忆历史对比，,只是栈顶元素可见，能力有限，且不灵活,2023/10/8,58,PDA可以是非确定型的，确定型PDA与非确定型PDA在语言识别能力上不相同，非确定型PDA能识别确定型PDA不能识别的一些语言，这与（非）确定型有穷自动机不相同。非确定型下PDA等价于上下文无关文法。,PDA类型,2023/10/8,59,下推自动机M被定义为七元组(Q,q0,Z0,F)(以终止状态接受语言)，或者(Q,q0,Z0,)(以空栈方式接受语言)，这里Q,和F都是有穷集Q是状态集是输入字母表栈字符表q0Q是起始状态FQ是接受状态(终止状态)集是状态转移函数Z0是初始栈顶符号：QP(Q*)=,PDA的形式化定义,2023/10/8,60,(q,a,Z)=(p1,r1),(p2,r2),(pm,rm)表示M在状态q，栈顶符号为Z时，读入字符a，对于i=1,2,m，可以选择地将状态变成pi，并将栈顶符号Z弹出，将i中的符号压入栈，然后将读头向右移动一个带方格而指向输入字符串的下一个字符,PDA的形式化定义,2023/10/8,61,(q,Z)=(p1,r1),(p2,r2),(pm,rm)表示M进行一次-移动(空移动)，即M在状态q，栈顶符号为Z时，无论输入符号是什么，对于i=1,2,m，可以选择地将状态变成pi，并将栈顶符号Z弹出，将ri中的符号从右到左依次压入栈，读头不移动,PDA的形式化定义,2023/10/8,62,下推自动机的瞬像是一个三元组(q,w,r)，其中q表示当前状态，w表示输入串中待扫描的子串，r表示下推栈中当前的内容(栈字符串)若(p,)(q,a,Z)，则有一步瞬像推导(q,aw,Zr)(p,w,r)。若用*表示下推自动机的若干步推导，则以空栈方式接受语言的的下推自动机M所接受的语言为N(M)=w*|(q0,w,Z0)*(p,)以终止状态接受语言的的下推自动机M所接受的语言为N(M)=w*|(q0,w,Z0)*(p,r),pF,PDA的形式化定义,2023/10/8,63,一台下推自动机M=(Q,q0,F)的计算过程如下：它接受输入，如果能够把写成=12m，这里i，并且存在序列r0,r1,rmQ和字符串序列s0，s1,sm*，满足下面三个条件，字符串si是M在计算的接受分支中的栈内容序列r0=q0，且s0=，表示M从初始状态和空栈开始对于i=0,1,m-1，有(ri+1,b)(ri,i+1,a)，其中si=at，si+1=bt，a，b，和t*rmF,PDA计算过程,2023/10/8,64,定理1：若语言L被一个以终止状态方式接受语言的PDA M2接受，当且仅当L被一个以空栈方式接受语言的PDA M1接受,PDA的等价性,2023/10/8,65,一个例子,例2.9:PDA对语言0n1n n0的识别读取输入串中的符号，每读一个0，把它推入栈一旦看见1之后，每读一个1，把一个0弹出栈当栈中的0被清空时恰好读完输入串，则接受如果还有1没有读完的时候栈已空，或栈未空输入串已经读完，或0出现在1之后，则拒绝。,2023/10/8,66,一个例子,例2.9:PDA识别语言L=0n1n|n0的转移函数(q1,)=(q2,$)(q2,0,)=(q2,0)(q2,1,0)=(q3,)(q3,1,0)=(q3,)(q3,$)=(q4,),2023/10/8,67,例2.9:L=0n1n|n0 背景：检查左右括号(0,1)是否配对PDA 首先把“$0n”推入栈.$栈底符号，表示后来压入栈的存款用完了然后，当读到“1n”,0被弹出.栈顶对比，左右括号配对，则同归于尽最后,如果“$”留在栈顶，则接受,一个例子,2023/10/8,68,一个记号,(q1,a,b)=(q2,c)：表示当状态q1下，机器从输入中读到a，并且栈顶符号b时，就用符号c替换符号b，并转移到状态q2。记为：(q1,a,b)(q2,c)，或写为a,bca,b,c中任何一个都可以为当a是时，则机器不读入任何符号，用符号c代替堆栈顶的b，并从状态q1转移到q2当b是时，则机器读入符号a，不从栈顶弹出任何符号，并压入符号c，并从状态q1转移到q2当c是时，则机器读入符号a，从栈顶弹出符号b，不压入任何符号，并从状态q1转移到q2,2023/10/8,69,PDA状态图描述,用“a,b c”表示当机器从输入中读a时可用c替换栈顶的符号b若a是，则机器作这个转移，而不读取输入中的任何符号。若b是，则机器作这个转移，而不读栈中的任何符号，也不从栈中弹出任何符号。若c是，则不在栈中写任何符号。,2023/10/8,70,w=000111,2023/10/8,71,w=0101,2023/10/8,72,问题：设计一个下推自动机接受语言L1=wcwR|w0,1*解题思路：L1中串是一个回文结构，中间以字母c分界读取输入串中的0或1，把它推入栈，状态不变一旦看见字母c之后，进入一个新状态在新状态下，当输入字母与栈顶符号相同，出栈，状态不变，直到输入结束与栈空同时出现，则接受如果如果输入字母与栈顶符号不相同，则拒绝,一个例子,2023/10/8,73,问题：设计一个下推自动机接受语言L1=wcwR|w0,1*解题：接受L1的下推自动机表示为：M1=(q1,q2,0,1,c R,0,1,q1,R,)其中为(q1,0,R)=(q1,0R);(q1,1,R)=(q1,1R);(q1,c,R)=(q2,R);(q1,0,0)=(q1,00);(q1,1,0)=(q1,10);(q1,c,0)=(q2,0);(q1,0,1)=(q1,01);(q1,1,1)=(q1,11);(q1,c,1)=(q2,1);(q2,1,1)=(q2,);(q2,0,0)=(q2,);(q2,R)=(q2,);例如输入串x=101c101，其推导过程：(q1,101c101,R)(q1,01c101,1R)(q1,1c101,01R)(q1,c101,101R)(q2,101,101R)(q2,01,01R)(q2,1,1R)(q2,R)(q2,),一个例子,2023/10/8,74,问题：设计一个接受语言L2=wwR|w0,1*的下推自动机解题：接受L2的下推自动机表示为：M2=(q1,q2,0,1 R,0,1,q1,R,)这是空栈方式接受语言。其中为(q1,0,R)=(q1,0R);(q1,1,R)=(q1,1R);(q1,0,0)=(q1,00),(q2,);(q1,1,0)=(q1,10);(q1,1,1)=(q1,11),(q2,);(q1,0,1)=(q1,01);(q2,1,1)=(q2,);(q2,0,0)=(q2,);(q2,R)=(q2,);(q1,R)=(q2,);,一个例子,2023/10/8,75,例如输入串x=001100，其推导过程：,一个例子,2023/10/8,76,问题：设计一个接受语言L2=wwR|w0,1*的下推自动机解题：接受L2的下推自动机表示为：M2=(q0,q1,q2 qf,0,1,X0,R,0,1,0,q0,X0,qf)这是终止状态接受语言。其中0为0(q0,X0)=(q0,RX0)0(q1,0,R)=(q1,0R);0(q1,1,R)=(q1,1R)0(q1,0,0)=(q1,00),(q2,);0(q1,1,0)=(q1,10)0(q1,1,1)=(q1,11),(q2,);0(q1,0,1)=(q1,01)0(q2,1,1)=(q2,);0(q2,0,0)=(q2,)0(q2,R)=(q2,);0(q1,R)=(q2,)0(q1,X0)=(qf,X0);0(q2,X0)=(qf,X0),一个例子,2023/10/8,77,计算过程,一个例子,2023/10/8,78,确定型PDA,设M=(Q,q0,Z0,F)是一个下推自动机，如果1）qQ,zF，当(q,Z)时，a,(q,a,Z)=2）不存在qQ，z和a使得(q,a,Z)有多于一个值，则称M为一个确定的下推自动机PDA，记为DPDA,2023/10/8,79,确定型PDA（说明）,PDA在每一个状态q和一个栈顶符号下的动作都是惟一的 关键每一种情况下的移动都是惟一的非确定的PDA和确定型PDA识别能力不同，非确定型PDA能识别确定型PDA不能识别的语言,2023/10/8,80,确定型PDA（说明）,一个下推自动机被称为确定的，需要满足两个条件确定型自动机不能在同一瞬像下产生两个以上推导，因此必须满足2）对于条件1），事实上，假设存在某个状态q和某个栈定元素Z，使得(q,Z)=(q1,r1)，同时存在a,(q,a,Z)=(q2,r2)，贼对于瞬像(q,aw,Zr)，就存在如下两个推导，从而违背了条件2）(q，aw，Zr)(q1，aw，r1r)(q，aw，Zr)(q1，w，r2r),2023/10/8,81,确定型PDA（说明）,以终止状态方式接受语言的DPDA和以空栈方式接受语言的DPDA两者并不等价，它们能够接受的语言类的范围并不相同。例如，对于语言L1=anbn|n1，既可以设计以终止状态方式接受语言的DPDA来接受它，也可以设计以空栈方式接受语言的DPDA来接受它。对于语言L2=anbn|n0，虽然可以设计以终止状态方式接受语言的DPDA来接受它，却无法设计以空栈方式接受语言的DPDA来接受它。,2023/10/8,82,广义的下推自动机,广义PDA是七元组(Q,q0,Z0,F)(以终止状态接受语言)，或者(Q,q0,Z0,)(以空栈方式接受语言)，这里Q,和F都是有穷集Q是有限状态集是输入字母表栈字符表q0Q是起始状态FQ是接受状态(终止状态)集Z0是初始栈顶符号是状态转移函数：Q+P(Q*)=,2023/10/8,83,广义的下推自动机,广义PDA和一般PDA的区别在于：它允许同时处理一串栈顶符号（弹出一串栈顶符号，压入一串栈符号），即状态转移函数形式如下：Q+P(Q*)=(q,x,B1B2Bk)=(q,C1C2Cn),2023/10/8,84,单态下推自动机,单态PDA是七元组(Q,q0,Z0,F)(以终止状态接受语言)，或者(Q,q0,Z0,)(以空栈方式接受语言)，这里,F和的定义和一般的不确定PDA一样，但状态集合Q中只有唯一状态单态PDA只有一个状态，对于转移函数(q,x,B)=(q,C)，则可改写成：(x,B)C，进一步地写成规则BxC对于转移函数(q,x,B)=(q,)，则可写成规则Bx,2023/10/8,85,与上下文无关文法的等价性,定理2.12：一个语言是上下文无关的，当且仅当存在一台PDA识别它。L是CFLL被PDA接受,2023/10/8,86,引理2.13,引理2.13：如果一个语言是上下文无关的，则存在一台PDA识别它。证明思路：设A是一个CFL，则存在一个CFG产生它，因此需要一个PDA去模仿CFG派生A中语言的过程PDA P开始时将起始变元写入栈中，然后对栈中的变元进行替换，经过一系列的中间字符串，最终它可能到达一个仅含有终结符的字符串，如果其与它接受到的字符串相同，则P接受它。,2023/10/8,87,证明思路,引理2.13：如果一个语言是上下文无关的，则存在一台PDA识别它。证明思路：由于PDA P必须不停的对其中变元进行替换，且其只能访问栈顶元素，因此栈中只保存中间字符串中从第一个变元开始的所有符号，对于其前面的终结符串必须不停地与输入符号串做匹配处理，即其必须与输入中的符号匹配，否则拒绝。,2023/10/8,88,证明思路,引理2.13：如果一个语言是上下文无关的，则存在一台PDA识别它。证明思路：PDA P的非形式描述如下：把标记符$和起始变元S入栈重复下述步骤：如果栈顶元素是变元A，则非确定地选择一个关于A的规则，并把A替换成其规则右边的字符串如果栈顶符号是终结符a，则读输入中的下一个符号，并且将其与a比较。如果匹配，则重复；否则拒绝这个非确定性分支如果栈顶符号是$，则进入接受状态，若输入恰好结束，则接受这个输入串,2023/10/8,89,证明关键,引理2.13：如果一个语言是上下文无关的，则存在一台PDA识别它。证明关键：构造PDA P=(Q,q1,F)如下：首先引入类似于GNFA的记法，使P能一次处理一个字符串，例如将规则右边整个写入栈，或将栈中第一个变元前所有终结符出栈,2023/10/8,90,证明关键,设q和r是P的状态，a，s，当P读入a并且弹出s的时候，状态从q变到r，并且同时将整个字符串u=u1u2ul入栈，可以引入新的状态q1,q2,ql-1并定义转移函数为(q1,ul)=(q,a,s),(q2,ul-1)(ql,),(q3,ul-2)(q2,(r,u1)(ql-1,)上面整个地写成(r,u)(q,a,s)表示当q是P的状态，a是下一个输入符号以及s是栈顶符号时，P能够读a和弹出s，然后将字符串u入栈并转移到状态r,2023/10/8,91,证明关键,2023/10/8,92,证明关键,引理2.13：如果一个语言是上下文无关的，则存在一台PDA识别它。证明关键：构造PDA P=(Q,q1,F)如下：P的状态集为qstart，qloop，qacceptE转移函数定义如下(qstart,)=(qloop,S$)(qloop,A)=(qloop,)|A是R中的一条规则(qloop,a,a)=(qloop,)(qloop,$)=(qaccept,),2023/10/8,93,证明关键,2023/10/8,94,例题,设L=L(G)，其中G的产生式集为SaA|a AaA|bA|a|bG是一个格雷巴赫范式，设计以空栈方式接受L的PDA为M=q,a,b,S,A,q,S,其中，(q,a,S)=(q,A),(q,)(q,a,A)=(q,A),(q,)(q,b,A)=(q,A),(q,),2023/10/8,95,例：CFG G 转换成PDA P,2023/10/8,96,引理2.15,引理2.15：如果一个语言能被一台PDA识别，则它是上下文无关的。证明思路：,2023/10/8,97,引理3,引理3：对任意一个以空栈方式接受语言的下推自动机PDA，都存在一个上下文无关文法G，使得L(G)=N(M)证明：设以空栈方式接受语言的下推自动机为M=(Q,q0,Z0,)构造上下文无关文法G=(V,R,S)V=QQS=q,A,p|p,qQ,AS产生式集R中的产生式包括,2023/10/8,98,引理3,引理3：对任意一个以空栈方式接受语言的下推自动机PDA，都存在一个上下文无关文法G，使得L(G)=N(M)证明：产生式集R中的产生式包括对qQ都有产生式Sq0,Z0,q若(q1,B1B2Bm)(q,a,A)，则有产生式q1,A,qm+1aq1,B1,q2q2,B2,q3qm,Bm,qm+1其中q1,q2,qm+1可以是Q中任意一个元素对推导的步数用数学归纳法证明(略)，p,qQ,A,x*都有q,A,p x当且仅当(q,x,A)*(p,)特别地有S*x当且仅当(q,x,Z0)*(p,),2023/10/8,99,引理4,引理4：对任意一个上下文无关语言L，都存在一个以空栈方式接受语言的下推自动机N，使得L=N(M)证明：1）假设产生一个L-上下文无关文法的格雷巴赫范式为G=(V,R,S)构造一个以空栈方式接受语言的下推自动机M=(q,V,q,S,)其中，对AV和a(q,a,A)=(q,r)|若Aar是G的产生式对输入串w的长度用数学归纳法可以证明(q,w,S)*(q,)当且仅当S*w,2023/10/8,100,引理4,引理4：对任意一个上下文无关语言L，都存在一个以空栈方式接受语言的下推自动机N，使得L=N(M)证明：先证必要性，即若(q,w,S)*(q,)，则必有S*w。当|w|=1时，设w=a，若(q,w,S)(q,)，则有(q,)(q,a,S)，由M的构造知Sa是G的一个产生式，从而有Sa的推导。设w=xa,从而(q,w,S)(q,)可以写成(q,w,S)=(q,xa,S)*(q,a,r)*(q,)由(q,xa,S)*(q,a,r)知有(q,x,S)*(q,r)。注意到|x|=k，从而由归纳假设知，文法G中存在推导S*xr。对于(q,a,r)*(q,)。设r=Ar2，则必存在动作函数(q,a,A)使得(q,1)(q,a,A)且=1r2。这样，就可写成(q,a,Ar2)(q,r2)。于是Aa1是G的一个产生式，从而G中存在推导Sxr=xAr2xa1r2=w，即S*w。这就证明了必要性,2023/10/8,101,引理4,引理4：对任意一个上下文无关语言L，都存在一个以空栈方式接受语言的下推自动机N，使得L=N(M)证明：充分性也可以类似地应用数学归纳法证明（略）。当=时，我