最新形式语言自动机——上下文无关文法与下推自动机(三)PPT课件.ppt

《最新形式语言自动机——上下文无关文法与下推自动机(三)PPT课件.ppt》由会员分享，可在线阅读，更多相关《最新形式语言自动机——上下文无关文法与下推自动机(三)PPT课件.ppt（26页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、形式语言自动机形式语言自动机上下文无关上下文无关文法与下推自动机文法与下推自动机(三三)CNF的构成步骤的构成步骤1.用算法用算法1、2、3、4消除消除生成式、无用符号、单生成式生成式、无用符号、单生成式2.对生成式对生成式AD1D2Dn n2 若若DiT，则引入新生成式则引入新生成式BiDi，Bi是新非终结符是新非终结符 若若DiN，则令则令BiDi，从而将原生成式变化为从而将原生成式变化为 AB1B2Bn n2 当当n2 时，再将其变为时，再将其变为 AB1C1，C1B2C2，C2B3C3，Cn1Bn1Bn Ci是新引入的非终结符。是新引入的非终结符。定理证明定理证明自学自学2Colleg

2、e 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 被变换为被变换为

3、（略）略）注意：新引入的注意：新引入的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 的语言无法由一般的有限自动机识别

4、。有限有限状态识别器中必须有无限个无限个状态 (不允许不允许!)!)需要需要扩扩充机器的能力。充机器的能力。aaaaabbbbbb识别anbn的无限状态自动机11College of Computer Science&Technology,BUPT下推自动机的结构下推自动机的结构n扩充办法：引入一个下推栈足够简单可解决许多有意义的问题，如识别有效的程序n下推自动机PDA（PushDownAutomaton）由一条输入带,一个有限状态控制器和一个下推栈组成nPDA的动作在有限状态控制器的控制下根据它的当前状态、栈顶符号、以及输入符号作出相应的动作。有时，不需要考虑输入符号（空转移）。n栈：后进先

5、出表对栈的操作（压入、弹出）均在栈顶进行。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，*表示在

6、状态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而言，初始格

7、局为（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时，从栈中弹

8、出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

9、/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）最多含一个元素。这两个限制防止了在动作和包含一个输入符号的动作之间做选择的可能性（即在同样状态，同样栈顶符号下最多只

10、能有一个选择。）确定的下推自动机（确定的下推自动机（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 Scien

11、ce&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

12、匹配。所构造的NPDAM利用两个不确定的分支实现不同的猜想。解：解：非确定的下推自动机（非确定的下推自动机（NPDANPDA）22College of Computer Science&Technology,BUPT ,z1/z0z1 a,z0/,z/,z/,z/,z/MMfq0qfqeq1定理定理4.4.1如果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)=(

13、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定理定理4.4.2如果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结束语结束语谢谢大家聆听！谢谢大家聆听！26