计算理论第2章去某范式版.ppt

第一部分 自动机与语言,第1章 正则语言研究内容有穷自动机非确定性正则表达式非正则语言,第2章 上下文无关文法,研究内容上下文无关文法概述下推自动机非上下文无关语言,上下文无关文法的引入,有穷自动机和正则表达式这两种不同但等价的描述语言的方法，虽然能描述许多语言，但还有一些简单的语言不能用它们描述，如：0n1n|n=0于是，需引入一种能力更强的描述语言数学模型上下文无关文法，它能够描述某些应用广泛的具有递归结构特征的语言,对任何语言L，有一个字母表，使得L*。L的具体组成结构是什么样的？一个给定的字符串是否为一个给定语言的句子?如果不是，它在结构的什么地方出了错？进一步地，这个错误是什么样的错？如何更正？。这些问题对有穷语言来说，比较容易解决。这些问题对无穷语言来说，不太容易解决。用文法作为相应语言的有穷描述不仅可以描述出语言的结构特征，而且还可以产生这个语言的所有句子,文法(grammar),例：1）哈尔滨是美丽的城市 2）北京是祖国的首都 3）集合是数学的基础 4）形式语言是很抽象的4个句子的主体结构=哈尔滨，北京，集合，形式语言=是美丽的城市，是祖国的首都，是数学的基础，是很抽象的=。,可以是 或者。=北京、哈尔滨、形式语言、集合、美丽的城市、祖国的首都、数学的基础。=是。=很抽象的。把取名为。,表示成形式是,表示一个语言，需要4种东西 形如的“符号”它们表示相应语言结构中某个位置上可以出现的一些内容。每个“符号”对应的是一个集合，在该语言的一个具体句子中，句子的这个位置上能且仅能出现相应集合中的某个元素。所以，这种“符号”代表的是一个语法范畴。所有的“规则”，都是为了说明的结构而存在，相当于说，定义的就是。,形如北京的“符号”它们是所定义语言的合法句子中将出现的“符号”。仅仅表示自身，称为终极符号。所有的“规则”都呈的形式 在产生语言的句子中被使用，称这些“规则”为产生式。,文法的形式定义,G=(V,R,S)V为变量(variable)的非空有穷集。AV，A叫做一个语法变量(syntactic Variable)，简称为变量，也可叫做非终极符号(nonterminal)。它表示一个语法范畴(syntactic Category)。为终极符(terminal)的非空有穷集。a，a叫做终极符。由于中变量表示语法范畴，中的字符是语言的句子中出现的字符，所以，有V=。SSV，为文法G的开始符号(start symbol)。,文法的形式定义,R为产生式(production)的非空有穷集合。R中的元素均具有形式，被称为产生式，读作：定义为。其中(V)+，且中至少有V中元素的一个出现。(V)*。称为产生式的左部，称为产生式的右部。产生式又叫做定义式或者语法规则。,文法例 1,例：以下四元组都是文法。(A，0，1，A01，A0A1，A1A0，A)。(A，0，1，A0，A0A，A)。(A，B，0，1，A01，A0A1，A1A0，BAB，B0，A)。(A，B，0，1，A0，A1，A0A，A1A，A)。(S，A，B，C，D,a，b，c，d,#，SABCD，Sabc#，AaaA，ABaabbB，BCbbccC，cCcccC，CDccd#，CDd#，CD#d，S)。,约定,对一组有相同左部的产生式1，2，n可以简单地记为：1|2|n读作：定义为1，或者2，或者n。并且称它们为产生式。1，2，n称为候选式(candidate)。,使用符号英文字母表较为前面的大写字母，如A，B，C，表示语法变量；英文字母表较为前面的小写字母，如a，b，c，表示终极符号；希腊字母，表示由语法变量和终极符号组成的行,推导(derivation),设G=(V,R,S)是一个文法，如果R，(V)*，则称在G中直接推导出。G 读作：在文法G中直接推导出。“直接推导”可以简称为推导(derivation)，也称推导为派生。,定义,语言(language)L(G)=w|w*且S*w 句子(sentence)wL(G)，w称为G产生的一个句子。句型(sentential form)G=(V，R，S)，对于(V)*，如果S*，则称是G产生的一个句型。,定义,句子w是从S开始，在G中可以推导出来的终极符号行，它不含语法变量。句型是从S开始，在G中可以推导出来的符号行，它可能含有语法变量。等价(equivalence)设有两个文法G1和G2，如果L(G1)=L(G2)，则称G1与G2等价。,文法的构造例1,例：构造文法G，使L(G)=0，1，00，11 G1：S0|1|00|11G2：SA|B|AA|BB，A0，B1G3：S0|1|0A|1B，A0，B1G4：SA|B|AA|BB，A0，B1G5：SA|B|BB，A0，B1，CACS21，C11，C2,文法的构造例2,L=0n|n1 G6：S0|0S L=0n|n0 G7：S|0SL=02n13n|n0 G8：S|00S111,文法的构造例 3,例：构造文法G9，使L(G9)=w|wa，b，z+。G9：SA|AS Aa|b|c|d|e|f|g|h|i|j|k|l|m|n|o|p|q|r|s|t|u|v|w|x|y|z 用SA|AS生成 An。不可以用Aa|b|c|z表示。Aa|b|c|d|e|f|g|h|i|j|k|l|m|n|o|p|q|r|s|t|u|v|w|x|y|z不可以用Aa8表示Aaaaaaaaa。不能用Aan表示A可以产生任意多个a。,文法的乔姆斯基体系,文法G=(V，R，S)G叫做0型文法(type 0 grammar)，也叫做短语结构文法(phrase structure grammar,PSG)。L(G)叫做0型语言。也可以叫做短语结构语言(PSL)、递归可枚举集(recursively enumerable，r.e.)。,文法的乔姆斯基体系,G是0型文法。如果对于R，均有|成立，则称G为1型文法(type 1 grammar)，或上下文有关文法(context sensitive grammar,CSG)。L(G)叫做1型语言(type 1 language)或者上下文有关语言(context sensitive language,CSL)。,文法的乔姆斯基体系,G是1型文法如果对于R，均有|，并且V成立，则称G为2型文法(type 2 grammar)，或上下文无关文法(context free grammar,CFG)。L(G)叫做2型语言(type 2 language)或者上下文无关语言(context free language,CFL)。,文法的乔姆斯基体系,G是2型文法如果对于R，均具有形式 Aw AwB其中A，BV，w+。则称G为3型文法(type 3 grammar)，也可称为正则文法(regular grammar,RG)或者正规文法。L(G)叫做3型语言(type 3 language)，也可称为正则语言或者正规语言(regular language,RL)。,文法的乔姆斯基体系,如果一个文法G是RG（3型文法），则它也是CFG（2型文法）、CSG（1型文法）和短语结构文法（0型文法）。反之不一定成立。如果一个文法G是CFG，则它也是CSG和短语结构文法。反之不一定成立。如果一个文法G是CSG，则它也是短语结构文法。反之不一定成立。相应地：RL也是CFL、CSL和短语结构语言。反之不一定成立。,文法的乔姆斯基体系,CFL也是CSL和短语结构语言。反之不一定成立。CSL也是短语结构语言。反之不一定成立 当文法G是CFG时，L(G)却可以是RL。当文法G是CSG时，L(G)可以是RL、CSL。当文法G是短语结构文法时，L(G)可以是RL、CSL和CSL。,定理,定理：L是RL（正则语言）的充要条件是存在一个文法，该文法产生语言L，并且它的产生式要么是形如：Aa的产生式，要么是形如AaB的产生式。其中A、B为语法变量，a为终极符号。,2.1 上下文无关文法概述,文法G=(V，R，S)被称为是上下文无关文法或2型文法。如果对于R，均有|，并且V成立。关键：对于AV，如果AP，则无论A出现在句型的任何位置，我们都可以将A替换成，而不考虑A的上下文。L(G)叫做2型语言(type 2 language)或者上下文无关语言(context free language,CFL)。,上下文无关文法示例,上下文无关文法示例,2.1.1 上下文无关文法的形式化定义,定义2.1 上下文无关文法是一个4元组 G=(V,R,S)V:一个有穷集，称为变元集:一个有穷集(V=)，称为终结符集 R:有穷规则集，V(V)*规则是 左一右多，或一分为多 SV:起始变元文法 G的语言可以表示为 L(G):L(G)=w*|S*w,上下文无关文法举例,2.1.2 上下文无关文法举例,2.1.3 设计上下文无关文法,2.1.3 设计上下文无关文法,利用正则考察子串利用递归,2.1.4 岐义性,如果文法以不同的方式产生同一个字符串，则称文法歧义地产生这个字符串，如果一个文法歧义地产生某个字符串，则称这个文法是歧义的,2.1.4 岐义性,定义2.4 如果字符串w在上下文无关文法G中有两个以上不同的最左派生，则称G歧义地产生字符串w，如果文法G歧义地产生某个字符串，则称G是歧义的；注意：有时对于一个歧义文法，能够找到一个产生相同语言的非歧义文法，但是，某些上下文无关语言只能用歧义文法产生，这样的语言称为固有歧义的。,2.1.5 乔姆斯基范式Chomsky Normal Form,定义2.5 称一个上下文无关文法 G=(V,R,S)为乔姆斯基范式，如果它的每一个规则具有如下形式A BC 一分为二或A a 或终极化其中，AV and B,CV S,and a,2.1.5 乔姆斯基范式Chomsky Normal Form,定理2.6 任一上下文无关文法 G=(V,R,S)为语言都可以用一个乔姆斯基范式的上下文无关文法产生,证明思路：1）添加一个新的起始变元S0；和规则S0S 2）考虑所有的诸如A 规则；R uAv,添加R uv；R uAvAw,添加R uvAw;R uAvw;R uvwR A,添加R 3）处理所有的单一规则；4）添加新的变元和规则，把留下的所有规则转换成合适的变元；,例,例,试将下列文法转换成等价的 CNF。SbA|aB AbAA|aS|a BaBB|bS|b,先引入变量Ba，Bb和产生式Baa，Bbb，完成第一步变换。SBbA|BaB ABbAA|BaS|a BBaBB|BbS|b Baa Bbb,引入新变量B1、B2 SBbA|BaBABbB1|BaS|aBBaB2|BbS|b Baa Bbb B1AA B2BB,不能因为原来有产生式A a和B b而放弃引进变量Ba、Bb和产生式Baa、Bbb。L(A)=x|xa，b+&x中a的个数比b的个数恰多1个。L(B)=x|xa，b+&x中b的个数比a的个数恰多1个。L(Ba)=a。L(Bb)=b。,习题,试将下列文法转换成等价的 CNF。SaBB|bAA BaBa|aa|AbbA|,2.2 下推自动机Pushdown Automata,下推自动机PDA：描述CFL（上下文无关语言）的设备PDA：“硬件”增加了栈（先进后出），使其能识别某些非正则语言PDA：与上下文无关文法等价,有穷自动机的物理模型,PDA的物理模型,FSC：表示状态和转移函数栈：“先进后出”的存储设备，能保存无限的信息量推入：向栈写一个符号弹出：从栈中删除一个符号,例,例,非形式化地描述关于语言0n1n|n=0的PDA如何工作的：,PDA 的形式化描述,输入,内部状态集合State set Q,PDA M 读带 w且 作栈操作取决于-输入 wi,输入字母表-栈 sj,栈字母表-状态 qk Q 状态集合PDA M:-调转到一个新的状态,-推入元素(非确定性地),PDA的基本结构,PDA应该含有三个基本结构存放输入符号串的输入带。存放文法符号的栈。有穷状态控制器。PDA的动作 在有穷状态控制器的控制下根据它的当前状态、栈顶符号、以及输入符号作出相应的动作，在有的时候，不需要考虑输入符号。,下推自动机M被定义为6元组(Q，q0，F)，这里Q，和F都是有穷集合，并且：Q 是状态集 是输入字母表 栈字符表 q0 Q是起始状态 F Q是接受状态集 是状态转移函数 相当于3种语句goto,push,pop:Q P(Q)=,2.2.1 PDA 的形式化定义,(q，a，Z)=(p1，1)，(p2，2)，(pm，m)表示M在状态q，栈顶符号为Z时，读入字符a，对于i=1，2，m，可以选择地将状态变成pi，并将栈顶符号Z弹出，将i中的符号从右到左依次压入栈，然后将读头向右移动一个带方格而指向输入字符串的下一个字符。,(q，Z)=(p1，1)，(p2，2)，(pm，m)表示M进行一次-移动(空移动)，即M在状态q，栈顶符号为Z时，无论输入符号是什么，对于i=1，2，m，可以选择地将状态变成pi，并将栈顶符号Z弹出，将i中的符号从右到左依次压入栈，读头不移动。,PDA 的计算过程,一台下推自动机M接受输入w，如果能够把w写成w=w1w2wm，这里每一个wi，并且存在状态序列r0,r1,rm Q和字符串序列s0,s1,sm T*满足下述3个条件，字符串si是M在计算的接受分支中的栈内容序列。r0 q0 且s0，对于i=0,m-1，有（ri+1，b）(ri，wi+1，a)其中si=at,si+1=bt,a,b T 和t T*；rm F,例2.9:L=0n1n|n0 背景：检查左右括号(0,1)是否 配对 PDA 首先把“$0n”推入栈.$栈底符号，压箱钱，表示后来压入栈的存款用完了。然后，当读到“1n”,0被弹出.栈顶对比，左右括号配对，则同归于尽，最后,如果“$”留在栈顶，则接受,2.2.2 PDA 举例,状态图描述,用“a,b c”表示当机器从输入中读a时可用c替换栈顶的符号b。若a是，则机器作这个转移，而不读取输入中的任何符号。若b是，则机器作这个转移，而不读栈中的任何符号，也不从栈中弹出任何符号。若c是，则不在栈中写任何符号。,形式化定义,w=000111,w=0101,例：构造一台识别下述语言的PDA M：aibjck i,j,k0 且 i=j 或 i=k,例,例：构造接受L=wwT|w0,1*的PDA。,确定的(deterministic)PDA,PDA在每一个状态q和一个栈顶符号下的动作都是惟一的。关键对于(q，Z)Q，M此时如果有非空移动，就不能有空移动。每一种情况下的移动都是惟一的。非确定的PDA和确定型PDA识别能力不同，非确定型PDA能识别确定型PDA不能识别的语言,与上下文无关文法的等价性,定理.12:一个语言是上下文无关的，当且仅当存在一台PDA识别它。L是CFL L被PDA接受,两步:1)引理.如果一个语言是上下文无关的，则存在一台PDA识别它 部分2)引理.5 如果一个语言被一台PDA识别，则它是上下文无关的 部分若干教材都说 此定理容易证明 但又略去证明，此定理的证明适合静心自学，不适合课堂讲解。可以先承认结论，读第二遍时再深入理解,引理2.13 的证明（）,引理2.13 如果一个语言是上下文无关的，则存在一台下推自动机识别它。证明思路 设A 是CFL，根据定义，存在一个CFG G产生它。说明如何把G转换成一台等价的PDA P。确定是否存在关于输入w的派生PDA P当G产生w时，接受这个输入。派生是当文法产生一个字符串时的替换序列，派生的每一步产生一个变元和终结符的中间字符串。设计P，以确定是否有一系列使用G的规则替换，能够从起始变元导出w 检验是否有关于w的派生。困难在于判断要替换，PDA的非确定性使得它能够猜想出正确的替换序列，在派生的每一步，非确定地选择关于某个变元的一条规则，并且对这个变元做替换。,P的非形式描述如下：1)把标记符$和起始变元放入栈中；2）重复下述步骤：如果栈顶是变元A，则非确定地选择一个关于A的规则，并且把A替换成这条规则右边的字符串；如果栈项是终结符a，则读输入中的下一个符号，并且把它与a进行比较。如果它们匹配，则重复，如果它们不匹配，则这个非确定性分支拒绝；如果栈顶是符号$，则进入接受状态，如果此刻输入已全部读完，则接受这个输入。,1）初始化栈，把符号$和S推入栈；2）a)栈顶是个变元；令(qloop,A)(qloop,w)A w是R中的一条规则 b)栈顶是个终结符。令(qloop,a,a)(qloop,)c)栈顶是空栈标记符$。令(qloop,$)(qaccept,),CFG G 转换成PDA P例：把下述CFG G转换成一台PDA：SaTb b TTa,引理2.15的证明（）自学,引理2.15 如果一个语言被一台下推自动机识别，则它是上下文无关的。证明思路 现有一台PDA P，要构造一个CFG G，它产生P接受的所有字符串。换言之，如果一个字符串能使P从它的起始状态转移到一个接受状态，则G应该产生这个字符串。为了获得这个结果，我们设计一个能做更多事情的文法。对于P的每一对状态p和q，文法有一个变元Apq。它产生所有能够把P从p和空栈一块带到q和空栈的字符串。可以看出不管栈的内容是什么，这样的字符串也能够把P从p带到q，并且保持栈的内容在状态q和在状态p时样。,引理2.15 的证明（）,为简化工作，对P作修改，使其具有以下三个特点。1）有唯一的接受状态qaccept。2）在接受之前清空栈。3）每一个转移把一个符号推入栈(推入动作)，或者把一个符号弹出栈(弹出动作)，但不同时做这两个动作。使P具有特点1和2较容易，使P具有特点3就要把每一个同时弹出和推入的转移替换成两个转移，中间要经过一个新的状态；把每一个既不弹出也不推入的转移替换成两个转移，先推入任意一个栈符号，然后再把它弹出。,引理2.1 证明（3）,设计G，使得Apq产生把P从p带到q并且以空栈开始和结束的所有字符串，了解P对这样的字符串如何运行。对于任一的字符串x，P的每个动作是推入或是弹出，但对空栈不能弹出，对x的第一个动作一定是推入。因结束时栈空，对x的最后一个动作一定是弹出。在P对x的计算过程 两情况：仅在开始和结束时，栈是空的；或者除开始和结束时之外，在计算中的某个地方，栈变成空的。如是前情况，最后弹出的符号一定就是开始时推入的那个符号。用规则ApqaArsb模拟前一种情况，其中a是在做第一个动作时读的输入符号，b是在做最后一个动作时读的输入符号，r是跟在p后面的状态，s是q的前一个状态。用规则ApqAprArq模拟后一种情况，其中r是栈在计算中间变成空的时候的状态。,正则语言与上下文无关语言的关系,Regularlanguages,context-free languages,?,0n1n,2.3 非上下文无关语言,语言 L=anbncn|n0 不是CFL证明此事需要新的泵定理（言多必重复）比喻：前后文无关的人格，我行我素，不受舆论左右，两岸猿声啼不住，轻舟已过万重山，则某些爱好和行为就会重复如：A*vAy:If S*uAz*uvAyz*uvxyz L,then S*uAz*uvAyz*uviAyiz*uvixyiz L as well,for all i=0,1,2,关于上下文无关语言的泵引理的思想：与RL不同，CFL 两处打圈，至少一处是真圈，,定理2.19：如果A是上下文无关语言，则存在数p（泵长度），使得A中任何一个长度不小于p的字符串s被划分成5段 s=uvxyz 且满足下述条件：1)对于每一个I=0，uvixyiz A/两处打圈2)|vy|1/真圈3)|vxy|p/扇出度小于泵长（变量未重复，不超过变量个数）,语法分析树,S AbbcBa*cbbccccaBca cbbccccacca 当树足够高时，有限的变量符就会被重复使用,语法分析树,A,A,u,v,x,y,z,S,路径高度超过变量个数时，至少一个变量符号被重复,uvxyz L 派生树足够高，分段记号,A,A,u,v,x,y,z,S,期待的中递归,uv2xy2z L,i=2 在上页基础上A再自己派生一次,A,u,v,x,y,z,R,A,A,v,x,y,S,uxz L,i=0,A,u,z,uvixyiz L for all i=0,1,2,S,x,例：用泵引理证明语言 B=anb n c n n0不是上下文无关的。反证法：假设B是CFL，令p是B的泵长度，根据泵引理，这个p一定存在，选取字符串s=apb p c p。泵引理称s能被抽取，划分为uvxyz；1）当v或y含有一种符号；2）当v或y含有一种以上符号时；,