Software Systems Atlas

中文

English

中文

English

主题

第 11 卷 / 第 3 章 / 第 2 课

3.2 下推自动机与 CFL 边界：一个栈能记住什么 ​

有限自动机只有固定数量的状态。给它增加一只后进先出的栈，机器就能记住任意有限深度的未完成结构：左括号、调用层级，或前半段尚未匹配的符号。

本课目标 ​

  • 解释 PDA 的状态、输入和栈操作；
  • 模拟 anbn 与平衡括号识别；
  • 理解 CFG 与非确定性 PDA 的等价关系；
  • 说清单栈模型的能力边界。

1. PDA 在有限控制旁增加一个栈 ​

一种常见形式把非确定性 PDA 写成七元组：

M=(Q,Σ,Γ,δ,q0,Z0,F).
  • Q：有限状态集合；
  • Σ：输入字母表；
  • Γ：栈字母表；
  • q0：起始状态；
  • Z0：初始栈符号；
  • F：接受状态集合；
  • δ：根据状态、下一个输入或 ε、栈顶，给出有限个可能的新状态与栈替换，也允许零个（该路径无法继续）。

可把转移写成：

δ(q,a,X)∋(p,γ),

含义是：在状态 q，读取 a（也可能不读输入），弹出栈顶 X，把 γ 压回，并进入 p。

不同教材对“栈顶写在左还是右”、是否允许一次压入字符串等记号有不同约定。本课轨迹把栈顶写在右边：按从左到右顺序压入字符串时，最后一个符号成为栈顶。固定约定后再追踪执行，否则同一条转移会被读反。

2. 识别 anbn ​

语言：

L={anbn∣n≥0}

可分两个阶段：

text
push 阶段：每读一个 a，压入标记 A
pop  阶段：第一次读到 b 后，每读一个 b，弹出一个 A
结束条件：输入耗尽，栈回到初始标记

对 aaabbb：

text
输入        状态    栈（右侧为栈顶）
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。

空输入也应接受，对应 n=0；第一次 b 既切换阶段，也必须弹出一个 A，不能只换状态忘记弹栈。上面的检查器在确认输入结束后检查底标记，若写成正式 PDA，还需对应的接受状态或清空底标记的转移。

“输入读完且栈空”与“输入读完且处于接受状态”是两种 PDA 接受定义。对非确定性 PDA，它们在语言表达能力上等价，但具体自动机不能未经转换就混用条件。

3. 平衡括号需要检查类型与顺序 ​

若只有一种括号，栈深度像计数器。存在 ()、[]、{} 多种括号时，栈还保存最近未闭合括号的类型：

python
PAIRS = {")": "(", "]": "[", "}": "{"}
OPENING = set(PAIRS.values())

def brackets_are_balanced(text: str, max_depth: int = 1000) -> bool:
    if max_depth < 0:
        raise ValueError("max_depth must be nonnegative")
    stack: list[str] = []
    for char in text:
        if char in OPENING:
            if len(stack) >= max_depth:
                raise ValueError("bracket depth budget exceeded")
            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("([)]")

该 Python 3.9+ 示例对结构错误返回 False，对超出深度预算抛出 ValueError，两种结果要区分。它按输入长度线性扫描，额外存储随实际嵌套深度增长；超过预算时会提前退出。

代码忽略非括号字符，这是一项输入策略，不是括号语言定义自动给出的行为。若它用于解析字符串字面量或注释，必须先经过正确词法处理，否则字符串中的 ) 可能被误当作结构符号。

4. CFG 与 NPDA 的等价关系 ​

上下文无关语言恰好是非确定性 PDA 能识别的语言。

从 CFG 构造 NPDA 的直觉是：

  1. 栈中保存尚未匹配的文法符号；
  2. 栈顶是非终结符时，非确定地选择一条产生式展开；若栈顶在右侧，就把右侧符号逆序压入，让最左符号下次先被处理；
  3. 栈顶是终结符时，必须与输入下一个符号相同并同时弹出；
  4. 输入与栈任务同时耗尽时接受。

反方向可把 PDA 的状态变化和栈行为编码进非终结符，构造等价 CFG。严格构造较繁琐，但它证明“递归产生规则”和“有限控制加一只栈”是同一语言类的两种视角。

5. 确定性 PDA 更弱 ​

确定性 PDA（DPDA）要求每个配置至多有一个合法动作，并限制输入转移与 ε 转移的冲突。DPDA 识别确定性上下文无关语言，它是 CFL 的真子类。

实际确定性解析器并不意味着“所有 CFG 都是确定性的”。语言和文法需要满足相应 LL/LR 等条件，或者工具采用通用/广义算法处理更广的 CFG。广义解析程序本身也可以是确定性程序；“用确定性算法处理”与“由一个 DPDA 识别”不是同一要求。

6. 一个栈不是任意内存 ​

栈只能访问顶部。它可以保存嵌套结构，却难以同时比较多个独立、同向增长的区段。

典型非 CFL：

{anbncn∣n≥0}.

处理完 a 与 b 的数量关系时，单栈留下的信息不足以再独立验证 c。严格证明通常使用 CFL 泵引理、Ogden 引理或闭包性质，而不是只说“看起来需要两个计数器”。

两个栈可以模拟图灵机：一个栈保存读写头左侧内容，另一个保存当前位置及右侧内容。增加第二只栈会让计算能力发生质变。

7. CFL 的闭包性质影响组合方式 ​

上下文无关语言对以下运算封闭：

  • 并集；
  • 连接；
  • Kleene 星；
  • 与正则语言求交。

例如 L1={anbncm∣n,m≥0} 和 L2={ambncn∣n,m≥0} 都是 CFL，但它们的交集要求三段数量同时相等，是非 CFL。

因此，一般 CFL 不对交集和补集封闭。这意味着不能假设把两个独立 CFG 约束“同时满足”后仍可由某个 CFG 轻松描述。

与正则语言求交封闭很实用：可用有限状态条件过滤上下文无关结构，而不跳出 CFL。

8. 栈与真实编译器调用栈不是一回事 ​

递归下降解析器通常借用语言运行时调用栈实现文法递归；LR 解析器显式维护状态栈。它们都与 PDA 有理论联系，但实际栈元素可能还包含 token 位置、语义值、AST 节点和错误恢复信息。

理论 PDA 假设栈无界；实际进程内存有限，过深嵌套可能造成栈溢出或资源耗尽。理论中的“还能再压一个”，内存分配器未必同意。解析不受信任输入时，应设置深度、节点数和总输入量限制。

常见误区 ​

  • PDA 的栈只是一个整数计数器：它还保存符号类型与后进先出顺序。
  • 所有 CFL 都能由确定性 PDA 识别：DPDA 对应的是更小的确定性 CFL 类。
  • 括号扫描器可以直接处理完整源代码：字符串、注释和转义会改变字符语义。
  • 理论上可解析就不存在资源风险：实际栈深和输入规模必须受限。

练习 ​

  1. 模拟 PDA 对 aabbb 的执行，指出第一次不可恢复的拒绝位置。
  2. 修改括号代码，使它报告错误位置、实际右括号和期望右括号。
  3. 写出回文语言 {wwR∣w∈{a,b}∗} 的 CFG，并解释 NPDA 在哪里需要非确定选择中点。
  4. 解释为什么“CFL 与正则语言求交仍是 CFL”可用于证明某些语言不是 CFL。

小结 ​

PDA 用一只栈保存尚未完成的递归结构，非确定性 PDA 与 CFG 在表达能力上等价。一个栈能处理任意有限嵌套，却不是随机访问内存，也不能表达所有多重计数关系。

下一章把栈换成可双向读写的工作带，并随即遇到另一条更深的边界：有些问题不是算得慢，而是不存在对所有输入都给出答案的算法。

Built with VitePress | Software Systems Atlas

Copyright 2026 Steven Yang