《形式语言与自动机》课件ch4.4.ppt

1、1School of Computer Science,BUPT4.4 下推自动机（下推自动机（PDA）n主要内容nPDA的基本概念。nPDA的构造举例。n用终态接受语言和用空栈接受语言的等价性。nPDA是上下文无关语言的接收器。n重点nPDA的基本定义及其构造nPDA与上下文无关语言等价n难点n根据PDA构造上下文无关文法。2School of Computer Science,BUPT问题的引出问题的引出 类似于an bn 的语言无法由一般的有限自动机识别。有限有限状态识别器中必须有无限个无限个状态 (不允许不允许!)!)需要扩充机器的能力。需要扩充机器的能力。aaaabbbbbb识别an

2、 bn 的无限状态自动机 3School of Computer Science,BUPT下推自动机的结构下推自动机的结构n扩充办法：引入一个下推栈足够简单可解决许多有意义的问题，如识别有效的程序n下推自动机PDA（PushDownAutomaton）由一条输入带,一个有限状态控制器和一个下推栈组成nPDA的动作在有限状态控制器的控制下根据它的当前状态、栈顶符号、以及输入符号作出相应的动作。有时，不需要考虑输入符号（空转移）。n栈：后进先出表对栈的操作（压入、弹出）均在栈顶进行。4School of Computer Science,BUPT下推自动机的定义下推自动机的定义nNPDA的形式定义

3、：七元组 M（Q，T，q0，z0，F）其中：Q：有限控制器的状态集合 T：有限输入字母表 ：有限下推栈字母表：Q （T）Q*当前状态 当前输入 当前栈顶符号 有限子集 q0：初始状态，q0Q z0：下推栈的起始符号，z0 F：终态集合，F Q5School of Computer Science,BUPT下推自动机的下推自动机的转换函数转换函数n转换函数(q，a，Z)(p，)q、pQ，aT，Z，*表示在状态q，输入字符a，且栈顶符Z时，转入状态p，栈顶符Z由代替，同时读头右移一格。n约定：的最左符号放在栈顶。表示下推栈的顶符被弹出如（q，a，Z）(p，)（q，Z）(p，)称为转换。即不考虑当前

4、输入字符，读头不移动，但控制器状态可以改变且栈顶符可以调整。6School of Computer Science,BUPT下推自动机的下推自动机的格局格局n格局：用于描述PDA的瞬时工作状况PDA格局(q,)其中T*，*q当前状态待输入串(时，表示输入字符已读完)下推栈中的内容(时表示栈已弹空)n(q，a，Z)(p，r)用格局可表示为 (q,a,Z)(p,r)对PDA而言，初始格局为（q0，z0）终止格局为（q，）qF，*7School of Computer Science,BUPT下推自动机接受的下推自动机接受的语言语言n两种接受方式n终态接受：L(M)=(q0，z0)*(q，)，qF,

5、*n空栈接受：L(M)=(q0，z0)*(q，),qQ（当空栈接受时，终止状态可为Q中任意状态，换言之，终止状态集是与状态无关的。此时，取F）8School of Computer Science,BUPT下推自动机例下推自动机例n例：构造PDA M，接受语言L(M)=anbnn0n思路：把输入的字符a入栈，当开始输入b时，从栈中弹出a，若a、b个数相同，则到达终态，且栈中空。n解：设PDA M（Q，T，q0，z0，F），Qq0，q1，q2 q0 初态；接受a q1状态；接受b q2状态；输入 回到q0 Ta,b,=z0,a,F=q0定义为：(q0，a，z0)=(q1，a z0)(q1，a，a

6、)=(q1，aa)(q1，b，a)=(q2，)(q2，z0)=(q0，)(q2，b，a)=(q2，)9School of Computer Science,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，）终态接受终态接受10School of Computer Science,BUPT若对于每个输入字

7、符，其后续状态都是确定的，就是DPDA（如前例）。nDPDA必须满足下述二个条件之一：对 qQ，z,aT有(q，a，z)最多含一个后续选择且（q，z）或者(q，a，z)且（q，z）最多含一个元素。这两个限制防止了在动作和包含一个输入符号的动作之间做选择的可能性（即在同样状态，同样栈顶符号下最多只能有一个选择。）确定的下推自动机（确定的下推自动机（DPDADPDA）11School of Computer Science,BUPT例：例：构造PDA M，接受语言L(M)=cTa,b*.解题思路：解题思路：从状态q0接受句子，将输入存到栈中，状态不变，直到看到中心标记c。当达到c时，将状态变为q1

8、，栈不变。将输入与下推栈匹配，状态不变，退栈，直至栈空。确定的下推自动机（确定的下推自动机（DPDADPDA）q0 c,Z/Z q1 ,z0/qf a,z/az a,a/b,z/bz b,b/该自动机的形式定义：见书P11612School of Computer Science,BUPT例：例：构造PDA M，接受语言L(M)=Ta,b*.(与前面的例子类似，区别在于中间没有标志”c”)解：解：非确定的下推自动机（非确定的下推自动机（NPDANPDA）q0 ,Z/Z q1 ,z0/qf a,z/az a,a/b,z/bz b,b/把“c，z/z”改为“，z/z”就引进了非确定性。因为机器可在

9、任何时刻进行这种转换。13School of Computer Science,BUPT例：例：构造PDA M，接受语言L(M)=ai bj ck i =j 或 i =k，且k0。解题思路：解题思路：与前例类似，利用不确定性，PDA可以猜想a应与b匹配还是与c匹配。所构造的NPDA M利用两个不确定的分支实现不同的猜想。解：解：非确定的下推自动机（非确定的下推自动机（NPDANPDA）14School of Computer Science,BUPT ,z1/z0z1 a,z0/,z/,z/,z/,z/MMfq0qfqeq1定理定理4.4.1 如果Lf是PDA Mf以终态接受的语言，必存在一个

10、PDA M以空栈接受语言L，使LLf证明：证明：设Mf（Q，T，q0，z0，F）构造PDA M（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(q1，z1)=(q0，z0z1)(将z1作为栈底符，进入Mf的起始状态)对所有qQ，aT,z令1(q，a，z)=(q，a，z)（即M模拟Mf的动作）15School of Computer Science,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 空栈接受 MMf