语言与计算理论导引 下推自动机
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
