3.2 下推自动机与 CFL 边界：一个栈能记住什么
有限状态守门机遇到层层嵌套的括号后束手无策，馆长为它加上一只只允许从顶端取放的栈。
有限自动机只有固定数量的状态。给它增加一只后进先出的栈，机器就能记住任意有限深度的未完成结构：左括号、调用层级，或前半段尚未匹配的符号。
本课目标
- 解释 PDA 的状态、输入和栈操作；
- 模拟 $a^nb^n$ 与平衡括号识别；
- 理解 CFG 与非确定性 PDA 的等价关系；
- 说清单栈模型的能力边界。
1. PDA 在有限控制旁增加一个栈
一种常见形式把非确定性 PDA 写成七元组：
$$ M=(Q,\Sigma,\Gamma,\delta,q_0,Z_0,F). $$
- $Q$：有限状态；
- $\Sigma$：输入字母表；
- $\Gamma$：栈字母表；
- $q_0$：起始状态；
- $Z_0$：初始栈符号；
- $F$：接受状态；
- $\delta$：根据状态、下一个输入或 $\varepsilon$、栈顶，给出若干可能的新状态与栈替换。
可把转移写成：
$$ \delta(q,a,X)\ni(p,\gamma), $$
含义是：在状态 $q$，读取 $a$（也可能不读输入），弹出栈顶 $X$，把 $\gamma$ 压回，并进入 $p$。
不同教材对“栈顶写在左还是右”、是否允许一次压入字符串等记号有不同约定。先固定约定再追踪执行，否则同一条转移会被读反。
2. 识别 $a^nb^n$
语言：
$$ L={a^nb^n\mid n\ge0} $$
可分两个阶段：
push 阶段：每读一个 a，压入标记 A
pop 阶段：第一次读到 b 后，每读一个 b，弹出一个 A
结束条件：输入耗尽，栈回到初始标记对 aaabbb：
输入 状态 栈（右侧为栈顶）
aaabbb push Z
aabbb push ZA
abbb push ZAA
bbb push ZAAA
bb pop ZAA
b pop ZA
ε pop Z还要显式拒绝以下情况：
- 在 pop 阶段再次遇到
a； - 读
b时没有可弹出的A； - 输入结束后栈里仍有
A。
“读完时栈空”与“进入接受状态”是两种 PDA 接受定义。对非确定性 PDA，它们在语言表达能力上等价，但具体自动机不能未经转换就混用条件。
3. 平衡括号需要检查类型与顺序
若只有一种括号，栈深度像计数器。存在 ()、[]、{} 多种括号时，栈还保存最近未闭合括号的类型：
PAIRS = {")": "(", "]": "[", "}": "{"}
OPENING = set(PAIRS.values())
def brackets_are_balanced(text: str) -> bool:
stack: list[str] = []
for char in text:
if char in OPENING:
stack.append(char)
elif char in PAIRS:
if not stack or stack.pop() != PAIRS[char]:
return False
return not stack
assert brackets_are_balanced("([]{})")
assert not brackets_are_balanced("([)]")代码忽略非括号字符，这是一项输入策略，不是括号语言定义自动给出的行为。若它用于解析字符串字面量或注释，必须先经过正确词法处理，否则字符串中的 ) 可能被误当作结构符号。
4. CFG 与 NPDA 的等价关系
上下文无关语言恰好是非确定性 PDA 能识别的语言。
从 CFG 构造 NPDA 的直觉是：
- 栈中保存尚未匹配的文法符号；
- 栈顶是非终结符时，非确定地选择一条产生式展开；
- 栈顶是终结符时，必须与输入下一个符号相同并同时弹出；
- 输入与栈任务同时耗尽时接受。
反方向可把 PDA 的状态变化和栈行为编码进非终结符，构造等价 CFG。严格构造较繁琐，但它证明“递归产生规则”和“有限控制加一只栈”是同一语言类的两种视角。
5. 确定性 PDA 更弱
确定性 PDA（DPDA）要求每个配置至多有一个合法动作，并限制输入转移与 $\varepsilon$ 转移的冲突。DPDA 识别确定性上下文无关语言，它是 CFL 的真子类。
实际确定性解析器并不意味着“所有 CFG 都是确定性的”。语言和文法需要满足相应 LL/LR 等条件，或工具必须采用广义解析保留多种可能。
6. 一个栈不是任意内存
栈只能访问顶部。它可以保存嵌套结构，却难以同时比较多个独立、同向增长的区段。
典型非 CFL：
$$ {a^nb^nc^n\mid n\ge0}. $$
处理完 a 与 b 的数量关系时，单栈留下的信息不足以再独立验证 c。严格证明通常使用 CFL 泵引理、Ogden 引理或闭包性质，而不是只说“看起来需要两个计数器”。
两个栈可以模拟图灵机：一个栈保存读写头左侧内容，另一个保存当前位置及右侧内容。增加第二只栈会让计算能力发生质变。
7. CFL 的闭包性质影响组合方式
上下文无关语言对以下运算封闭：
- 并集；
- 连接；
- Kleene 星；
- 与正则语言求交。
但一般不对 CFL 之间的交集和补集封闭。这意味着不能假设把两个独立 CFG 约束“同时满足”后仍可由某个 CFG 轻松描述。
与正则语言求交封闭很实用：可用有限状态条件过滤上下文无关结构，而不跳出 CFL。
8. 栈与真实编译器调用栈不是一回事
递归下降解析器通常借用语言运行时调用栈实现文法递归；LR 解析器显式维护状态栈。它们都与 PDA 有理论联系，但实际栈元素可能还包含 token 位置、语义值、AST 节点和错误恢复信息。
理论 PDA 假设栈无界；实际进程内存有限，过深嵌套可能造成栈溢出或资源耗尽。解析不受信任输入时，应设置深度、节点数和总输入量限制。
常见误区
- PDA 的栈只是一个整数计数器：它还保存符号类型与后进先出顺序。
- 所有 CFL 都能由确定性 PDA 识别：DPDA 对应的是更小的确定性 CFL 类。
- 括号扫描器可以直接处理完整源代码：字符串、注释和转义会改变字符语义。
- 理论上可解析就不存在资源风险：实际栈深和输入规模必须受限。
练习
- 模拟 PDA 对
aabbb的执行，指出第一次不可恢复的拒绝位置。 - 修改括号代码，使它报告错误位置、实际右括号和期望右括号。
- 写出回文语言 ${ww^R\mid w\in{a,b}^*}$ 的 CFG，并解释 NPDA 在哪里需要非确定选择中点。
- 解释为什么“CFL 与正则语言求交仍是 CFL”可用于证明某些语言不是 CFL。
小结
PDA 用一只栈保存尚未完成的递归结构，非确定性 PDA 与 CFG 在表达能力上等价。一个栈能处理任意有限嵌套，却不是随机访问内存，也不能表达所有多重计数关系。
下一章把栈换成可双向读写的工作带，并随即遇到另一条更深的边界：有些问题不是算得慢，而是不存在对所有输入都给出答案的算法。