形式语言与自动机课件——Chomsky范式和Greibach范式

1、1College of Computer Science & Technology, BUPT 4.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 Sc

2、ience & Technology, BUPT CNF 的构成步骤的构成步骤 1. 用算法用算法1、2、3、4消除消除生成式、无用符号、单生成式生成式、无用符号、单生成式 2. 对生成式对生成式AD1D2Dn n2 若若DiT，则引入新生成式则引入新生成式BiDi，Bi是新非终结符是新非终结符 若若DiN，则令则令BiDi，从而将原生成式变化为从而将原生成式变化为 AB1B2Bn n2 当当n2 时，再将其变为时，再将其变为 AB1C1，C1B2C2，C2B3C3，Cn 1Bn1Bn Ci是新引入的非终结符。是新引入的非终结符。 定理证明定理证明自学自学 3College of Comput

3、er Science & Technology, BUPT CNF 的构成例的构成例 例例: (书书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，

4、C C2 2BBBB. 4College of Computer Science & Technology, BUPT CNF 的构成例的构成例 例例: 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，增加增加EBBEBB 5College of Com

5、puter Science & Technology, BUPT GreibachGreibach范式范式 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, BUPT GNF 的构成步骤的构成步骤 1. 将将2 2型文法变换为型文法变换为CNFCNF。（。（AaAa，ABCABC形式）形式） 2.2.将非终结符排序将非终结符排

6、序, ,再进行代换。再进行代换。 对形如对形如A Ai iAAj j（jijili）。）。 3.3.消左递归。消左递归。 对最高的对最高的A An nAAn n进行变换，使进行变换，使A An n生成式变为终结符开头。生成式变为终结符开头。 4.4.回代。回代。 将将A An n生成式回代入生成式回代入A An n 1 1生成式，使其右部首符为终结符， 生成式，使其右部首符为终结符， 将将A An n 1 1生成式回代入 生成式回代入A An n 2 2生成式，使其右部首符为终结符 生成式，使其右部首符为终结符 5.5. 最后将消直接左递归时引入的最后将消直接左递归时引入的A A1 1、 A

7、A2 2、AAn n生成式右部生成式右部 进行代换。使其首符变为终结符。进行代换。使其首符变为终结符。 7College of Computer Science & Technology, BUPT GNF 的构成例的构成例 例例: (书书P149 例例2) 设已有设已有CNF： ABCABC， BCAb BCAb， CABa CABa， 将其变换为将其变换为GNF。 解解: 按其非终结符排列为按其非终结符排列为A A、B B、C C，A A是低位，是低位，C C是高位。是高位。 、中，右部首符序号高于左部的非终结符、中，右部首符序号高于左部的非终结符 无需变换。无需变换。 对，需要变换，对，

8、需要变换， 将代入得将代入得 CBCBa CBCBa ， 仍需变换，仍需变换， 将代入得将代入得 CCACBbCBa CCACBbCBa 8College of Computer Science & Technology, BUPT GNF 的构成例的构成例 对上述变换后所得结果消直接左递归对上述变换后所得结果消直接左递归 对对CCCCACBACBbCBbCBa a 变换为变换为 1 1 1 1 2 2 C C1 12 21 1CC2 2CC C C 1 11 1 C C 即即 CbCBabCBC aC CbCBabCBC aC CACBACBC CACBACBC 9College of Co

9、mputer Science & Technology, BUPT GNF 的构成例的构成例 回代回代 将将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 被变换为被变换为 （

10、略）略） 注意：新引入的注意：新引入的A Ai i相当于排在最低位。相当于排在最低位。 10College of Computer Science & Technology, BUPT 4.4 下推自动机（下推自动机（PDA） n主要内容 nPDA的基本概念。 nPDA的构造举例。 n用终态接受语言和用空栈接受语言的等价性。 nPDA是上下文无关语言的接收器。 n重点 nPDA的基本定义及其构造 nPDA与上下文无关语言等价 n难点 n根据PDA构造上下文无关文法。 11College of Computer Science & Technology, BUPT 问题的引出问题的引出 类似于a

11、n bn 的语言无法由一般的有限自动机识别。 有限有限状态识别器中必须有无限个无限个状态 (不允许不允许!)!) 需要扩充机器的能力。需要扩充机器的能力。 a aa a a b bb b b b 识别an bn 的无限状态自动机 12College of Computer Science & Technology, BUPT 下推自动机的结构下推自动机的结构 n扩充办法：引入一个下推栈 足够简单 可解决许多有意义的问题， 如识别有效的程序 n下推自动机PDA（Push Down Automaton） 由一条输入带,一个有限状态控制器和一个下推栈组成 nPDA的动作 在有限状态控制器的控制下根据

12、它的当前状态、栈顶符号、以 及输入符号作出相应的动作。有时，不需要考虑输入符号（空 转移）。 n栈：后进先出表 对栈的操作（压入、弹出）均在栈顶进行。 13College of Computer Science & Technology, BUPT 下推自动机的定义下推自动机的定义 nNPDA的形式定义： 七元组 M（Q，T，q0，z0，F） 其中：Q：有限控制器的状态集合 T：有限输入字母表 ：有限下推栈字母表 ： Q （T） Q* 当前状态 当前输入 当前栈顶符号 有限子集 q0：初始状态，q0Q z0：下推栈的起始符号，z0 F： 终态集合，F Q 14College of Comput

13、er 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，) 称为转换。 即不考虑当前输入字符，读头不移动，但控制器状态可以 改变且栈顶符可以调整。 15College of Computer Science & Technology, BUPT 下推自动机的下推自动机的格局格局 n格局：用于描述PD

14、A的瞬时工作状况 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两种接受方式 n终态接受： L(M)= (q0 ，z0)* (q，) ，qF,* n空栈接受： L(M)= (q0 ，z0) * ( q，), qQ （当空

15、栈接受时，终止状态可为Q中任意状态，换言之， 终止状态集是与状态无关的。此时，取F） 17College of Computer Science & Technology, BUPT 下推自动机例下推自动机例 n例：构造PDA M，接受语言L(M)= anbnn1 n思路：把输入的字符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 z

16、0) (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/ q0 q2q1 用格局表示aabb的识别过程: (q0 ，aabb，z0) （q1，abb，az0） （q1，bb，aaz0） （q2，

17、b，az0） （q2，z0） （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 C

18、omputer Science & Technology, BUPT 例：例：构造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/ 该自动机的形式定义：见书P157 21College of Computer Science & Technology, BUPT 例

19、：例：构造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”就引进了非确定性。因 为机器可在任何时刻进行这种转换。 22College of Computer Science & Technology, BUPT 例：例：构造PDA M，接受语言L(M) = ai bj ck i = j 或 i = k。 解题思路：解题思路： 与前例类似，利用不确定性，PDA可以猜想a应与b匹配还是与c匹配。 所构造的NPDA M利用两个不确定的分支实现不同的猜想。 解：解： 非确定的下推自动机（非确定的下推自动机（NPDANPDA） 23College of Computer Science & Technology, BUPT ,z1/z0z1 a, z0/ ,z/,z/ ,z/,z/ M Mf q0 qf qeq1 定理定理4.4.1 如果Lf是PDA Mf以终态接受的语言，必存在一个PDA M以空栈 接受语言L，使L