形式语言自动机-上下文无关文法与下推自动机.ppt
4.3 Chomsky范式和范式和Greibach范式范式nChomsky范式定义：n 2型文法型文法G（N，T，P，S），），若生成式形式都若生成式形式都是是ABC和和Aa，A、B、C N，a T，则则G是是Chomsky范式。若范式。若 L（G），），则则S是是P的一的一个生成式，但个生成式，但S不能在任何其它生成式的右边。不能在任何其它生成式的右边。n每个上下文无关文法都具有等效的每个上下文无关文法都具有等效的CNF（定理定理4.3.1）1College of Computer Science&Technology,BUPTCNF 的构成步骤的构成步骤1.用算法用算法1、2、3、4消除消除生成式、无用符号、单生成式生成式、无用符号、单生成式2.对生成式对生成式AD1D2Dn n2 若若DiT，则引入新生成式则引入新生成式BiDi，Bi是新非终结符是新非终结符 若若DiN，则令则令BiDi，从而将原生成式变化为从而将原生成式变化为 AB1B2Bn n2 当当n2 时，再将其变为时，再将其变为 AB1C1，C1B2C2，C2B3C3，Cn1Bn1Bn Ci是新引入的非终结符。是新引入的非终结符。定理证明定理证明自学自学2College of Computer Science&Technology,BUPTCNF 的构成例的构成例 例例:(书书P148 例例1)设设G（A，B，S，a，b，P，S）是无是无、无循环、无无循环、无无用符号、无单生成式的文法。无用符号、无单生成式的文法。P：SaAB BA ABBB a BAS b 求等效的求等效的CNF G1解解：SBASBA，AaAa，BAS,BbBAS,Bb已是已是CNFCNF 加入到加入到P P1 1中中对对SaABSaAB，将其变换为将其变换为SCSCa aC C1 1，C Ca aaa，C C1 1ABAB 将将ABBBABBB变换为变换为ABCABC2 2，C C2 2BBBB.3College of Computer Science&Technology,BUPTCNF 的构成例的构成例 例例:2 2型文法型文法G G（AA，B B，SS，aa，bb，P P，S S）P:SbAaB AbAAaSa BaBBbSb P:SbAaB AbAAaSa BaBBbSb 求等效的求等效的CNFCNF解解：SCSCb bACACa aB B，增加增加C Cb bbb，C C2 2aa AC ACb bDCDCa aSaSa，增加增加DAADAA BC BCa aECECb bSbSb，增加增加EBBEBB4College of Computer Science&Technology,BUPTGreibachGreibach范式范式nGreibach范式(GNF)定义：n2型文法G（N，T，P，S），若生成式的形式都是Aa，AN，aT，N*，且G不含生成式，则称G为Greibach范式，记为GNF。n 任何2型文法都具有等效的GNF（定理4.3.2）5College of Computer Science&Technology,BUPTGNF 的构成步骤的构成步骤1.将将2 2型文法变换为型文法变换为CNFCNF。（。（AaAa，ABCABC形式）形式）2.2.将非终结符排序将非终结符排序,再进行代换。再进行代换。对形如对形如A Ai iAAj j（jijili）。）。3.3.消左递归。消左递归。对最高的对最高的A An nAAn n进行变换，使进行变换，使A An n生成式变为终结符开头。生成式变为终结符开头。4.4.回代。回代。将将A An n生成式回代入生成式回代入A An n1 1生成式，使其右部首符为终结符，生成式，使其右部首符为终结符，将将A An n1 1生成式回代入生成式回代入A An n2 2生成式，使其右部首符为终结符生成式，使其右部首符为终结符 5.5.最最后后将将消消直直接接左左递递归归时时引引入入的的A A1 1、A A2 2、AAn n生生成成式式右右部部进行代换。使其首符变为终结符。进行代换。使其首符变为终结符。6College of Computer Science&Technology,BUPTGNF 的构成例的构成例 例例:(书书P149 例例2)设已有设已有CNF：ABCABC，BCAb BCAb，CABa CABa，将其变换为将其变换为GNF。解解:按其非终结符排列为按其非终结符排列为A A、B B、C C，A A是低位，是低位，C C是高位。是高位。、中，右部首符序号高于左部的非终结符中，右部首符序号高于左部的非终结符 无需变换。无需变换。对对，需要变换，需要变换，将将代入代入得得 CBCBa CBCBa ，仍需变换，仍需变换，将将代入代入得得 CCACBbCBa CCACBbCBa 7College of Computer Science&Technology,BUPTGNF 的构成例的构成例 对上述变换后所得结果消直接左递归对上述变换后所得结果消直接左递归 对对CCCCACBACBbCBbCBa a 变换为变换为 1 1 1 1 2 2 C C1 12 21 1CC2 2CCC C 1 11 1 C C即即 CbCBabCBC aC CbCBabCBC aC CACBACBC CACBACBC 8College of Computer Science&Technology,BUPTGNF 的构成例的构成例 回代回代将将C C的生成式的生成式回代入回代入B B的生成式的生成式 BBC CAb Ab 被变换为被变换为 BbCBAaAbCBCAaCAb BbCBAaAbCBCAaCAb 将新的将新的B B生成式生成式回代入回代入A A的生成式的生成式 AAB BC C 被变换为被变换为 AbCBACaACbCBCACaCACbC AbCBACaACbCBCACaCACbC 再将新的再将新的A A生成式生成式代入新引入的代入新引入的CC生成式生成式 CCA ACBCBA ACBC CBC 被变换为被变换为 （略）略）注意：新引入的注意：新引入的A Ai i相当于排在最低位。相当于排在最低位。9College of Computer Science&Technology,BUPT4.4 下推自动机（下推自动机（PDA）n主要内容nPDA的基本概念。nPDA的构造举例。n用终态接受语言和用空栈接受语言的等价性。nPDA是上下文无关语言的接收器。n重点nPDA的基本定义及其构造nPDA与上下文无关语言等价n难点n根据PDA构造上下文无关文法。10College of Computer Science&Technology,BUPT问题的引出问题的引出 类似于an bn 的语言无法由一般的有限自动机识别。有限有限状态识别器中必须有无限个无限个状态 (不允许不允许!)!)需要需要扩扩充机器的能力。充机器的能力。aaaaabbbbbb识别anbn的无限状态自动机11College of Computer Science&Technology,BUPT下推自动机的结构下推自动机的结构n扩充办法：引入一个下推栈足够简单可解决许多有意义的问题，如识别有效的程序n下推自动机PDA（PushDownAutomaton）由一条输入带,一个有限状态控制器和一个下推栈组成nPDA的动作在有限状态控制器的控制下根据它的当前状态、栈顶符号、以及输入符号作出相应的动作。有时，不需要考虑输入符号（空转移）。n栈：后进先出表对栈的操作（压入、弹出）均在栈顶进行。12College of Computer Science&Technology,BUPT下推自动机的定义下推自动机的定义nNPDA的形式定义：七元组 M（Q，T，q0，z0，F）其中：Q：有限控制器的状态集合T：有限输入字母表：有限下推栈字母表：Q（T）Q*当前状态当前输入 当前栈顶符号有限子集 q0：初始状态，q0Qz0：下推栈的起始符号，z0F：终态集合，FQ13College of Computer Science&Technology,BUPT下推自动机的下推自动机的转换函数转换函数n转换函数(q，a，Z)(p，)q、pQ，aT，Z，*表示在状态q，输入字符a，且栈顶符Z时，转入状态p，栈顶符Z由代替，同时读头右移一格。n约定：的最左符号放在栈顶。表示下推栈的顶符被弹出如（q，a，Z）(p，)（q，Z）(p，)称为转换。即不考虑当前输入字符，读头不移动，但控制器状态可以改变且栈顶符可以调整。14College of Computer Science&Technology,BUPT下推自动机的下推自动机的格局格局n格局：用于描述PDA的瞬时工作状况PDA格局(q,)其中*，*q当前状态待输入串(时，表示输入字符已读完)下推栈中的内容(时表示栈已弹空)n(q，a，Z)(p，r)用格局可表示为(q,a,Z)(p,r)对PDA而言，初始格局为（q0，z0）终止格局为（q，）qF，*15College of Computer Science&Technology,BUPT下推自动机接受的下推自动机接受的语言语言n两种接受方式n终态接受：L(M)=(q0，z0)*(q，)，qF,*n空栈接受：L(M)=(q0，z0)*(q，),qQ（当空栈接受时，终止状态可为Q中任意状态，换言之，终止状态集是与状态无关的。此时，取F）16College of Computer Science&Technology,BUPT下推自动机例下推自动机例n例：构造PDAM，接受语言L(M)=anbnn1n思路：把输入的字符a入栈，当开始输入b时，从栈中弹出a，若a、b个数相同，则到达终态，且栈中空。n解：设PDAM（Q，T，q0，z0，F），Qq0，q1，q2q0初态；接受aq1状态；接受bq2状态；输入 回到q0 Ta,b,=z0,a,F=q0定义为：(q0，a，z0)=(q1，a z0)(q1，a，a)=(q1，aa)(q1，b，a)=(q2，)(q2，z0)=(q0，)(q2，b，a)=(q2，)17College of Computer Science&Technology,BUPT下推自动机的图形表示下推自动机的图形表示 n上例的图形表示：q a,Z/p表示（p，）（q，a，Z）注：栈空就不能再移动了a,z0/az0 b,a/a,a/aa b,a/,z0/q0q2q1用格局表示aabb的识别过程:(q0，aabb，z0)（q1，abb，az0）（q1，bb，aaz0）（q2，b，az0）（q2，z0）（q0，）终态接受终态接受18College of Computer Science&Technology,BUPT若对于每个输入字符，其后续状态都是确定的，就是DPDA（如前例）。nDPDA必须满足下述二个条件之一：对 qQ，z,aT有(q，a，z)最多含一个后续选择且（q，Z）或者(q，a，z)且（q，z）最多含一个元素。这两个限制防止了在动作和包含一个输入符号的动作之间做选择的可能性（即在同样状态，同样栈顶符号下最多只能有一个选择。）确定的下推自动机（确定的下推自动机（DPDADPDA）19College of Computer Science&Technology,BUPT例：例：构造PDAM，接受语言L(M)=cTa,b*.解题思路：解题思路：从状态q0接受句子，将输入存到栈中，状态不变，直到看到中心标记c。当达到c时，将状态变为q1，栈不变。将输入与下推栈匹配，状态不变，退栈，直至栈空。确定的下推自动机（确定的下推自动机（DPDADPDA）q0c,Z/Z q1 ,z0/qfa,z/az a,a/b,z/bz b,b/该自动机的形式定义：见书P15720College of Computer Science&Technology,BUPT例：例：构造PDAM，接受语言L(M)=Ta,b*.(与前面的例子类似，区别在于中间没有标志”c”)解：解：非确定的下推自动机（非确定的下推自动机（NPDANPDA）q0,Z/Z q1 ,z0/qfa,z/az a,a/b,z/bz b,b/把“c，z/z”改为“，z/z”就引进了非确定性。因为机器可在任何时刻进行这种转换。21College of Computer Science&Technology,BUPT例：例：构造PDAM，接受语言L(M)=aibjcki=j或i=k。解题思路：解题思路：与前例类似，利用不确定性，PDA可以猜想a应与b匹配还是与c匹配。所构造的NPDAM利用两个不确定的分支实现不同的猜想。解：解：非确定的下推自动机（非确定的下推自动机（NPDANPDA）22College of Computer Science&Technology,BUPT ,z1/z0z1 a,z0/,z/,z/,z/,z/MMfq0qfqeq1定理定理如果Lf是PDAMf以终态接受的语言，必存在一个PDAM以空栈接受语言L，使LLf证明：证明：设Mf（Q，T，q0，z0，F）构造PDAMf（Qqe,q1，T，z1，1，q1，z1，）用M模拟Mf空栈接受与终态接受的等价空栈接受与终态接受的等价 对所有qf F和z z1 1(qf，z)=(qe，)（当Mf进入终态时，用转换进入qe状态，弹出栈顶）在qe状态下，若栈不为，则不断弹出栈顶符，直至栈空1定义：1(q1，z1)=(q0，z0z1)(将z1作为栈底符，进入Mf的起始状态)对所有qQ，aT,z令1(q，a，z)=(q，a，z)（即M模拟Mf的动作）23College of Computer Science&Technology,BUPT定理定理如果L是PDAM 以空栈接受的语言，必存在一个PDAMf以终态接受语言L，使 Lf L证明：证明：设M（Q，T，q0，z0，）构造PDAMf（Qq0f,qf，T，z1，f，q0f，z1，qf）空栈接受与终态接受的等价空栈接受与终态接受的等价 f定义：f(q0f，z1)=(q0，z0z1)f(q，a，z)=(q，a，z)f(q，z1)=(qf，)q 0f ，z1/z0z1 q0 a,z0/,z1/q f 空栈接受MMf24College of Computer Science&Technology,BUPT作业：作业：ch4ch4习题习题.11 11、151525College of Computer Science&Technology,BUPT
