第 6 章下推自动机

有限控制 + 栈：CFG 的机器模型

Source scope
主要依据教材第 6 章：中文印刷页 151–175，对应 PDF p.164–188/189。教材依次讨论 PDA 的定义、两种接受方式、PDA 与 CFG 等价以及确定型 PDA。

1 0. 为什么 DFA 不够、栈为什么刚好

要识别

\[ \{0^n1^n\mid n\ge0\}, \]

机器必须记住前面出现了多少个 0。DFA 只有有限状态，做不到无界计数。

PDA（pushdown automaton）在有限控制器之外加入一个后进先出栈。它不需要记住精确整数，只需对每个 0 压一个标记，随后每读一个 1 弹一个标记。

2 1. PDA 的正式定义

一个非确定型 PDA 写成

\[ P=(Q,\Sigma,\Gamma,\delta,q_0,Z_0,F), \]

其中：

\(Q\)：有限状态集；
\(\Sigma\)：输入字母表；
\(\Gamma\)：栈字母表；
\(q_0\)：初态；
\(Z_0\)：初始栈符号；
\(F\)：接受状态集；
转移函数 \[ \delta:Q\times(\Sigma\cup\{\varepsilon\})\times\Gamma \to \mathcal P(Q\times\Gamma^*). \]

2.1 1.1 如何读一个转移

若

\[ (p,\gamma)\in\delta(q,a,X), \]

表示：

当前状态 \(q\)；
若下一输入是 \(a\)（或 \(a=\varepsilon\) 不消耗输入）；
栈顶为 \(X\)；
则可转到 \(p\)；
弹出 \(X\)，并把字符串 \(\gamma\) 压回栈顶。

若 \(\gamma=\varepsilon\)，就是单纯弹栈。

3 2. 瞬时描述 ID

PDA 的配置不仅由状态决定，还必须记录：

未读输入；
栈内容。

写作

\[ (q,w,\alpha). \]

例如

\[ (q,011,AZ_0) \]

表示当前在状态 \(q\)，剩余输入 011，栈顶为 \(A\)，下面是 \(Z_0\)。

一步移动记为 \(\vdash_P\)，多步记为 \(\vdash_P^*\)。

4 3. 例：识别 \(\{0^n1^n\}\)

设计思想：

读 0 阶段：每个 0 压入一个 \(X\)；
第一次读 1 时切换阶段；
读 1 阶段：每个 1 弹出一个 \(X\)；
输入读完且只剩底符号时接受。

核心不变量：

进入第二阶段前，栈中 \(X\) 的个数等于已读 0 的个数；进入第二阶段后，剩余 \(X\) 个数等于“0 的总数减去已读 1 的个数”。

5 4. 两种接受方式

教材讨论两种常用定义。

5.1 4.1 终态接受

输入全部读完后处于某个接受状态：

\[ (q_0,w,Z_0)\vdash^*(q,\varepsilon,\alpha),\quad q\in F. \]

栈可以不空。

5.2 4.2 空栈接受

输入全部读完，并把栈清空：

\[ (q_0,w,Z_0)\vdash^*(q,\varepsilon,\varepsilon). \]

此时不依赖接受状态集合。

5.3 4.3 两者表达能力相同

对非确定型 PDA：

\[ \boxed{\text{final-state acceptance}\equiv\text{empty-stack acceptance}} \]

5.3.1 空栈 → 终态

加入新底符号与新接受状态。当旧栈已经清到新底符号时，转入新终态。

5.3.2 终态 → 空栈

加入新底符号；一旦旧 PDA 进入接受状态，就转入“清栈状态”，通过 \(\varepsilon\) 转移不断弹出栈符号直至空栈。

6 5. CFG 到 PDA

给定 CFG \(G=(V,T,P,S)\)，可以构造 PDA 模拟“猜测一个推导”。

基本思想：

栈顶若是变量 \(A\)，非确定地选择产生式 \[A\to\alpha\] 并把 \(A\) 替换为 \(\alpha\)；
栈顶若是终结符 \(a\)，必须与输入下一个字符 \(a\) 匹配，然后同时消费输入与弹栈；
输入与栈同时耗尽则接受。

PDA 的非确定性对应“文法有多个产生式可选”。

7 6. PDA 到 CFG

反向构造更技术化。核心变量常编码：

\[ [pXq] \]

含义可以理解为：

从状态 \(p\) 出发、栈顶有 \(X\)，经过某段输入后恰好弹掉 \(X\) 并到达状态 \(q\) 的所有字符串。

根据 PDA 的转移组合建立产生式，最终得到与 PDA 相同的语言。

因此：

\[ \boxed{\text{PDA}\equiv\text{CFG}\equiv\text{CFL}}. \]

8 7. 确定型 PDA（DPDA）

PDA 的非确定性不是装饰。对 DFA，NFA 与 DFA 等价；但对 PDA：

\[ \text{DPDA 的语言} \subsetneq \text{CFL}. \]

确定型 PDA 要求，在给定状态和栈顶符号时，不能同时存在会冲突的输入转移和 \(\varepsilon\) 转移。

8.1 7.1 正则语言与 DPDA

每个正则语言都能被 DPDA 识别：直接忽略栈，用有限控制模拟 DFA 即可。

8.2 7.2 DPDA 与文法歧义

确定型 CFL 与无歧义文法有紧密关系。特别地，确定型 CFL 一定存在无歧义 CFG；但一般 CFL 可能固有歧义。

9 8. 常见错误

忘记 PDA 的转移依赖栈顶符号；
把 \(\varepsilon\) 输入转移理解成“读到字符 epsilon”；
没有区分输入是否已读完与栈是否为空；
终态接受时误以为栈必须空；
空栈接受时误以为必须进入某个双圈状态；
认为 NFA 与 DFA 等价，所以 NPDA 与 DPDA 也一定等价；这是错误的。

10 9. 本章关系图

CFG  --construct-->  NPDA
 ^                  |
 |                  v
 +----construct-----+

NPDA final-state acceptance = NPDA empty-stack acceptance
Regular ⊂ DCFL ⊂ CFL