语言与计算理论导引 下推自动机
7 下推自动机
7.1 以例子为导引
本章我们研究如何拓展有限自动机,引出能够处理 CFL 的抽象机模型。我们已经发现了
许多不是正则语言的 CFL(当然,也有很多 CFL 是正则语言)。我们的讨论不妨从下面的例
子开始。
例子 7.1 CFG G 有如下的产生式:SaSa | bSb | c,G 生成的语言是 L={xcx
r
| x{a, b}*}。
分析:显然 L 中的字符串也属于回文语言,还多一个特征,即字符串的中央是一个特别的
字符 c。现在我们要设计一个识别 L 的算法。假设我们从左至右扫描字符串,很显然在遇到字
符 c 之前,我们需要保存见到的每个字符,一旦遇到了字符 c,则将当前的字符与先前保存的
字符进行比较,注意比较时,采用的是“后保存,先比较”的原则,或者称为“后来先出”原则
(last in, first out. LIFO)。实现 LIFO 原则的数据结构是栈,它的形式是一个链表,只通过一
端处理链表,这个端称为栈顶(top),链表的元素在 top 端加入到链表中(push,压入),
或从链表里删除(pop,弹出)。
上面的算法虽然简单,却包含了我们将要设计的处理 CFL 的抽象机模型的基本要素。由
于无限状态的抽象机很难描述,因此我们保留 FA 状态的有限性,但是我们增加辅助的存储空
间,并假设它是无限大的。前面已经看到有限空间的抽象机无法识别回文语言这样的 CFL。因
此总的来说,新的抽象机包含两部分空间,有限的状态和无限的栈,同时抽象机的移动方法也
要做相应的扩充。决定移动动作的因素从 FA 的两个增加到三个,即状态、输入字符和栈顶内
容,同时移动动作除了状态的转移,还包括栈顶的处理。
在这个简单例子中,状态集包括三个状态:q0、q1 和 q2。q0 是初始状态,抽象机在扫描
过程中,遇到 c 之前,始终停留在状态 q0,而且不断将遇到的字符加入到栈中;当遇到 c,则
状态转移到 q1,保持栈不变。在随后的扫描中,保持状态为 q1,且不断比较栈顶字符与遇到
的字符,如果相同,将栈顶字符弹出,继续上面的过程,否则抽象机崩溃(crash),输入的字
符串不能被接受。如果没有崩溃,且最后读入的字符,使得栈为空,则抽象机状态转到
q2。q2 是本例抽象机的接受状态,如果字符串最后到达了 q2,则字符串被接受。
总结上面,抽象机的每一步由下面三方面决定:
1. 当前状态
2. 下一个输入字符
3. 栈顶的符号
抽象机的移动包含两方面:
1. 状态转移(包括转移到自身)
2. 改变栈顶内容,将栈顶符号用一个符号串代替,或用空串代替
我们可以更严格地限制栈顶处理的规则,比如只允许压入或弹出操作。显然允许一次性地
将栈顶符号替换成符号串仅仅是栈顶基本操作的多次处理,不会改变抽象机的实际能力,但带
来的好处是使得描述转移函数的转移表大大简化了,因此我们设计的抽象机允许栈顶稍许复杂
的操作。栈的弹出相当于用空字符代替栈顶符号,栈的压入,比如栈顶符号为 X,压入符号为
Y,相当于用 XY 代替 X。而栈顶符号 X 被符号串代替,可以看成是一个弹出操作和多个压
入操作的组合过程。
FA 的转移函数定义是,: QxQ,上面的抽象机将其扩充成,: QxxQx*。其中,
是输入符号的字母表,是栈中符号的字母表,这两个字母表可以相同,也可以不同,也可
以部分字符相同。比如状态 q,在输入字符 a 和栈顶符号为 X 的转移结果可以写成,(q, a,
X)=(p, ),它的含义是转移到状态 p,且用符号串替换栈顶符号 X。
上面抽象机的一些细节还需要说明。首先当栈为空时,如何定义抽象机的移动,我们可以
通过定义栈底有一个特殊的初始符号 Z0,且 Z0 永远不会被弹出,来避免栈底为空的情况的出
陶晓鹏 Copyright 2003
1