为有限自动机添加一个栈

由于存在一些非正则语言，我们现在将研究一种能够接受其中部分语言的机器。这种机器在本质上与有限自动机相同，但额外增加了一个外部栈数据结构作为辅助存储，它被称为下推自动机（PDA）。下推自动机所接受的语言类称为上下文无关语言（CFL）。我们还将看到，与正则语言不同，非确定性与确定性的上下文无关语言之间存在差异：某些上下文无关语言本质上就是非确定性的。

在有限自动机中添加栈

有了栈之后，我们在处理输入流时可以选择从栈顶弹出符号和/或向栈中压入符号。状态转移取决于当前状态、读取的输入符号以及栈顶的符号。当执行一个转移时，我们不仅可以改变状态，还可以弹出一个符号，并压入一个或多个符号到栈中。PDA中的转移边形式为 <读取字符>,<弹出字符> → <压入字符串>。下图展示了一个接受语言 $L = \{a^nb^n\;|\;n>0\}$ 的下推自动机。

![接受语言 L 的 PDA]

我们总是从空栈开始运行。上述PDA的核心思想是：每读取一个 $a$，就在栈顶压入一个 $X$ 作为计数标记；每当读取一个 $b$ 时，就根据相应的转移规则从栈中弹出一个 $X$。只有当PDA最终进入接受状态并且栈为空时，才接受该输入字符串。

转移规则 $a, \lambda \rightarrow X$ 的含义是：“如果从输入流中读取到字符 $a$，则不从栈中弹出任何符号，并将一个 $X$ 压入栈中。”

注意：我们使用右箭头是因为一般来说，这相当于用要压入的一串符号替换栈顶的某个符号，类似于文法中的产生式规则（也使用右箭头）。如果你觉得画箭头麻烦，也可以用斜杠表示，例如 $b,X/\lambda$，或者直接用逗号分隔：$b,X,\lambda$。

转移规则中出现 $\lambda$ 表示忽略读取、压入或弹出操作，具体取决于它在规则中的位置。箭头前的符号表示要弹出的单个符号，箭头后的字符串表示要压入的符号串。如果期望弹出的符号不在栈顶，则该转移规则无法应用；如果没有可用的转移规则，机器就会“崩溃”（类似于进入陷阱状态），从而拒绝输入。在PDA中我们通常不显式地写出陷阱状态。

记住：PDA处理一个字符串必须以接受状态结束且栈为空，才能判定该字符串被接受。每次最多只能从栈中弹出一个符号。

下表追踪了输入字符串 $aabb$ 在上述PDA中的处理过程：

栈的内容在第三列中以字符串形式表示，其中最左边的字符代表栈顶。目标是消耗完整个输入字符串后停留在状态 $q_1$ 且栈为空，后者起到了基本的计数作用。

下推自动机的实现

下面的代码实现了上述PDA：

1def anbn(s):
2    state = 'q0'
3    stack = list()
4    for c in s:
5        if state == 'q0':
6            if c == 'a':
7                stack += 'X'
8            elif c == 'b':
9                try:
10                    top = stack.pop()
11                except:
12                    return False
13                assert top == 'X'
14                state = 'q1'
15            else:
16                return False
17        elif state == 'q1':
18            if c == 'b':
19                try:
20                    top = stack.pop()
21                except:
22                    return False
23                assert top == 'X'
24            else:
25                return False            
26    return state == 'q1' and not stack
27
28s = 'aabb'
29print(s,'accepted' if anbn(s) else 'not accepted')    # aabb accepted

代码解释

以下是上述代码的逐行说明：

• 第1行：定义函数 anbn，接收一个字符串 s 作为输入。
• 第2行：初始化变量 state 为 'q0'，用于记录当前状态。
• 第3行：初始化一个空列表作为栈，用来模拟栈的操作。
• 第4行：开始遍历输入字符串 s 中的每一个字符 c。
• 第5–7行：若当前状态为 'q0' 且字符为 'a'，则将 'X' 压入栈。
• 第8–14行：若当前状态为 'q0' 且字符为 'b'，则尝试从栈中弹出栈顶元素（若栈为空则返回 False），检查弹出的是 'X'，并将状态更新为 'q1'。
• 第15–16行：若当前状态为 'q0' 且字符既不是 'a' 也不是 'b'，则返回 False。
• 第17–23行：若当前状态为 'q1' 且字符为 'b'，则尝试弹出栈顶元素（若栈为空则返回 False），并验证其为 'X'。
• 第24–25行：若当前状态为 'q1' 且字符不是 'b'，则返回 False。
• 第26行：循环结束后执行此语句。仅当当前状态为 'q1' 且栈为空时返回 True，否则返回 False。
• 第28–29行：定义测试字符串 'aabb'，调用 anbn 函数判断其是否被接受，并输出结果。

我们也可以使用符号记号而非表格来表示PDA处理输入字符串的过程。符号 $\vdash$（有时读作“导出”或“产生”）表示机器的一个步骤进展。上面表格对应的符号表示为：

$$(q_0,aabb,\lambda) \vdash (q_0,abb,X) \vdash (q_0,bb,XX) \vdash (q_1,b,X) \vdash (q_1,\lambda,\lambda)$$

作为一种简写，我们可以对转门符号应用Kleene星号，表示整个运行过程：$(q_0,aabb,\lambda) \vdash^* (q_1, \lambda, \lambda)$。符号 $\vdash^*$ 表示“经过多步导出”。PDA的目标是从初始配置 $(q_0, s, \lambda)$ 开始（其中 $s$ 是输入字符串），最终到达某个终态 $q_f$ 且栈为空，即达到配置 $(q_f, \lambda, \lambda)$——换句话说：$(q_0, s, \lambda) \vdash^* (q_f, \lambda, \lambda)$。

接下来我们来看下推自动机的形式化定义。

下推自动机（PDA）的形式化定义

一个下推自动机（PDA）是一个带有附加栈的有限状态机，包含以下组成部分：

• $Q$：一组状态，其中一个是初始状态（起始状态），还有一个子集为终止状态（接受状态）。
• $\Sigma$：输入符号的字母表。
• $\Gamma$：栈字母表（可以包含 $\Sigma$ 中的符号）。
• $\delta: Q \times (\Sigma \cup \{\lambda\}) \times (\Gamma \cup \{\lambda\}) \to$ 有限子集 $Q \times \Gamma^*$，这是一个关系，表示给定当前状态、一个可选的输入字符（来自 $\Sigma$）和一个可选的栈顶字符（来自 $\Gamma$），可以确定下一状态以及要压入栈的 $\Gamma^*$ 中的字符串。

输入字母表和栈字母表不必互斥。此外，$\delta$ 是一个关系，意味着对于相同的输入可能有多个输出（属于 $Q \times \Gamma^*$），因此这一定义允许非确定性的存在。我们可以形式化地写出上图PDA的转移关系如下：

$$\begin{align*} \delta(q_0,a,\lambda) & = (q_0,X) \\ \delta(q_0,b,X) & = (q_1,\lambda) \\ \delta(q_1,b,X) & = (q_1,\lambda) \end{align*}$$

也可以用集合形式表示为：

$$\delta=\left\{ \left( (q_0,a,\lambda),(q_0,X)\right),\left( (q_0,b,X),(q_1,\lambda)\right), \left( (q_1,b,X),(q_1,\lambda)\right) \right\}$$

这个PDA恰好是确定性的，因此此时 $\delta$ 实际上是一个函数。

下面这个PDA接受语言 $M = \{a^nb^{2n}\;|\;n \ge 0\}$。

![接受语言 M 的 PDA]

对于每个读取的 $a$，我们向栈中压入两个 $X$，因此需要两倍数量的 $b$ 才能将栈清空。两个状态都是接受状态，因为 $n$ 可以为零，但请记住：只有当栈为空时，字符串才会被接受。