1、1College of Computer Science&Technology,BUPT4.3 Chomsky范式和范式和Greibach范式范式nChomsky范式定义：n 2型文法型文法G（N，T，P，S），），若生成式形式都若生成式形式都是是ABC和和Aa，A、B、CN，aT，则则G是是Chomsky范式。若范式。若L（G），），则则S是是P的一的一个生成式，但个生成式，但S不能在任何其它生成式的右边。不能在任何其它生成式的右边。n每个上下文无关文法都具有等效的每个上下文无关文法都具有等效的CNF（定理定理4.3.1）2College of Computer Science&Techno
2、logy,BUPTCNF 的构成步骤的构成步骤1.用算法用算法1、2、3、4消除消除生成式、无用符号、单生成式生成式、无用符号、单生成式2.对生成式对生成式AD1D2Dn n2 若若DiT，则引入新生成式则引入新生成式BiDi，Bi是新非终结符是新非终结符 若若DiN，则令则令BiDi，从而将原生成式变化为从而将原生成式变化为 AB1B2Bn n2 当当n2 时，再将其变为时，再将其变为 AB1C1，C1B2C2，C2B3C3，Cn1Bn1Bn Ci是新引入的非终结符。是新引入的非终结符。定理证明定理证明自学自学3College of Computer Science&Technology,B
3、UPTCNF 的构成例的构成例 例例:(书书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.4College of Computer Scienc
4、e&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，增加增加EBBEBB5College of Computer Science&Technology,BUPTGreibachGreibach范式范式
5、n Greibach范式(GNF)定义：n2型文法G（N，T，P，S），若生成式的形式都是Aa，AN，aT，N*，且G不含生成式，则称G为Greibach范式，记为GNF。n 任何2型文法都具有等效的GNF（定理4.3.2）6College of Computer Science&Technology,BUPTGNF 的构成步骤的构成步骤1.将将2 2型文法变换为型文法变换为CNFCNF。（。（AaAa，ABCABC形式）形式）2.2.将非终结符排序将非终结符排序,再进行代换。再进行代换。对形如对形如A Ai iAAj j（jijili）。）。3.3.消左递归。消左递归。对最高的对最高的A A
6、n 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生成式右部生成式右部进行代换。使其首符变为终结符。进行代换。使其首符变为终结符。7College of Computer Science&Tech
7、nology,BUPTGNF 的构成例的构成例 例例:(书书P149 例例2)设已有设已有CNF：ABCABC，BCAb BCAb，CABa CABa，将其变换为将其变换为GNF。解解:按其非终结符排列为按其非终结符排列为A A、B B、C C，A A是低位，是低位，C C是高位。是高位。、中，右部首符序号高于左部的非终结符、中，右部首符序号高于左部的非终结符 无需变换。无需变换。对，需要变换，对，需要变换，将代入得将代入得 CBCBa CBCBa ，仍需变换，仍需变换，将代入得将代入得 CCACBbCBa CCACBbCBa 8College of Computer Science&Tech
8、nology,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 9College of Computer Science&Technology,BUPTGNF 的构成例的构成例 回代回代将将C C的生成式回代入的生成式回代入B B的生成式的生成式 BBC CAb Ab 被变换为被变换为 BbCBAaAbCB
9、CAaCAb BbCBAaAbCBCAaCAb 将新的将新的B B生成式回代入生成式回代入A A的生成式的生成式 AAB BC C 被变换为被变换为 AbCBACaACbCBCACaCACbC AbCBACaACbCBCACaCACbC 再将新的再将新的A A生成式代入新引入的生成式代入新引入的CC生成式生成式 CCA ACBCBA ACBC CBC 被变换为被变换为 （略）略）注意：新引入的注意：新引入的A Ai i相当于排在最低位。相当于排在最低位。10College of Computer Science&Technology,BUPT4.4 下推自动机（下推自动机（PDA）n主要内容n
10、PDA的基本概念。nPDA的构造举例。n用终态接受语言和用空栈接受语言的等价性。nPDA是上下文无关语言的接收器。n重点nPDA的基本定义及其构造nPDA与上下文无关语言等价n难点n根据PDA构造上下文无关文法。11College of Computer Science&Technology,BUPT问题的引出问题的引出 类似于an bn 的语言无法由一般的有限自动机识别。有限有限状态识别器中必须有无限个无限个状态 (不允许不允许!)!)需要扩充机器的能力。需要扩充机器的能力。aaaaabbbbbb识别an bn 的无限状态自动机 12College of Computer Science&T
11、echnology,BUPT下推自动机的结构下推自动机的结构n扩充办法：引入一个下推栈 足够简单 可解决许多有意义的问题，如识别有效的程序n下推自动机PDA（Push Down Automaton）由一条输入带,一个有限状态控制器和一个下推栈组成nPDA的动作 在有限状态控制器的控制下根据它的当前状态、栈顶符号、以及输入符号作出相应的动作。有时，不需要考虑输入符号（空转移）。n栈：后进先出表对栈的操作（压入、弹出）均在栈顶进行。13College of Computer Science&Technology,BUPT下推自动机的定义下推自动机的定义nNPDA的形式定义：七元组 M（Q，T，q0
12、，z0，F）其中：Q：有限控制器的状态集合 T：有限输入字母表 ：有限下推栈字母表 ：Q （T）Q*当前状态 当前输入 当前栈顶符号 有限子集 q0：初始状态，q0Q z0：下推栈的起始符号，z0 F：终态集合，F Q14College 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，)称为转换。即不考
13、虑当前输入字符，读头不移动，但控制器状态可以改变且栈顶符可以调整。15College 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，*16College of Computer Science&Technology,BUPT下推自动机接受的下推自动机接受的语言语言n两种接
14、受方式n终态接受：L(M)=(q0，z0)*(q，)，qF,*n空栈接受：L(M)=(q0，z0)*(q，),qQ（当空栈接受时，终止状态可为Q中任意状态，换言之，终止状态集是与状态无关的。此时，取F）17College of Computer Science&Technology,BUPT下推自动机例下推自动机例n例：构造PDA M，接受语言L(M)=anbnn1n思路：把输入的字符a入栈，当开始输入b时，从栈中弹出a，若a、b个数相同，则到达终态，且栈中空。n解：设PDA M（Q，T，q0，z0，F），Qq0，q1，q2 q0 初态；接受a q1状态；接受b q2状态；输入 回到q0 Ta
15、,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，)18College 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，z
16、0）（q0，）终态接受终态接受19College of Computer Science&Technology,BUPT若对于每个输入字符，其后续状态都是确定的，就是DPDA（如前例）。nDPDA必须满足下述二个条件之一：对 qQ，z,aT有(q，a，z)最多含一个后续选择且（q，Z）或者(q，a，z)且（q，z）最多含一个元素。这两个限制防止了在动作和包含一个输入符号的动作之间做选择的可能性（即在同样状态，同样栈顶符号下最多只能有一个选择。）确定的下推自动机（确定的下推自动机（DPDADPDA）20College of Computer Science&Technology,BUPT例：例：
17、构造PDA M，接受语言L(M)=cTa,b*.解题思路：解题思路：从状态q0接受句子，将输入存到栈中，状态不变，直到看到中心标记c。当达到c时，将状态变为q1，栈不变。将输入与下推栈匹配，状态不变，退栈，直至栈空。确定的下推自动机（确定的下推自动机（DPDADPDA）q0 c,Z/Z q1 ,z0/qf a,z/az a,a/b,z/bz b,b/该自动机的形式定义：见书P15721College of Computer Science&Technology,BUPT例：例：构造PDA M，接受语言L(M)=Ta,b*.(与前面的例子类似，区别在于中间没有标志”c”)解：解：非确定的下推自动
18、机（非确定的下推自动机（NPDANPDA）q0 ,Z/Z q1 ,z0/qf a,z/az a,a/b,z/bz b,b/把“c，z/z”改为“，z/z”就引进了非确定性。因为机器可在任何时刻进行这种转换。22College of Computer Science&Technology,BUPT例：例：构造PDA M，接受语言L(M)=ai bj ck i =j 或 i =k。解题思路：解题思路：与前例类似，利用不确定性，PDA可以猜想a应与b匹配还是与c匹配。所构造的NPDA M利用两个不确定的分支实现不同的猜想。解：解：非确定的下推自动机（非确定的下推自动机（NPDANPDA）23Coll
19、ege of Computer Science&Technology,BUPT ,z1/z0z1 a,z0/,z/,z/,z/,z/MMfq0qfqeq1定理定理4.4.1 如果Lf是PDA Mf以终态接受的语言，必存在一个PDA M以空栈接受语言L，使LLf证明：证明：设Mf（Q，T，q0，z0，F）构造PDA Mf（Q qe,q1，T，z1，1，q1，z1，）用M模拟Mf空栈接受与终态接受的等价空栈接受与终态接受的等价 对所有qf F和z z1 1(q f，z)=(q e，)（当M f进入终态时，用转换进入qe状态，弹出栈顶）在q e状态下，若栈不为，则不断弹出栈顶符，直至栈空 1定义：1
20、(q1，z1)=(q0，z0z1)(将z1作为栈底符，进入Mf的起始状态)对所有qQ，aT,z令1(q，a，z)=(q，a，z)（即M模拟Mf的动作）24College of Computer Science&Technology,BUPT定理定理4.4.2 如果L是PDA M 以空栈接受的语言，必存在一个PDA M f 以终态接受语言L，使 Lf L证明：证明：设M（Q，T，q0，z0，）构造PDA Mf（Q q0f,qf，T，z1，f，q 0f，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 空栈接受 MMf25College of Computer Science&Technology,BUPT作业：作业：ch4ch4习题习题.11 11、1515
