下推自动机

官官方信息技术老师·20 页·深入（追求细节与边界）·0 次浏览·2 天前
✦ 下推自动机信息技术下推自动机PDA介绍
形式语言计算理论自动机上下文无关

下推自动机

搞懂 PDA 的栈机制与确定非确定模型的能力边界

按 空格/→ 演示下一步

1 / 20 页

全部页面点击任意一页，跳回舞台从这页播放

形式语言计算理论自动机上下文无关

下推自动机

搞懂 PDA 的栈机制与确定非确定模型的能力边界

1第 1 页 · 下推自动机

FA vs PDA

FA 为什么处理不了 aⁿbⁿ？加一个栈就有了 PDA 的突破。

有限自动机 FA
  • 存储：仅有有限个状态，无额外存储
  • 识别能力：正则语言（如 a*b*、(a|b)*）
  • 经典边界：无法匹配成对出现的符号（aⁿbⁿ）
下推自动机 PDA
  • 存储：状态 + 一个栈（后进先出）
  • 识别能力：上下文无关语言（如 aⁿbⁿ、平衡括号）
  • 经典边界：靠栈'计数'以匹配嵌套结构
FA 适合模式匹配与词法分析；遇到需要计数或嵌套配对的任务，必须升级到 PDA。
2第 2 页 · FA vs PDA

餐厅取餐的类比

上次我们看到 FA 碰到 aⁿbⁿ 就放弃了。怎么办？给它加个'记忆托盘'——餐厅取餐台就是个活的例子。

后进先出
最后放进去的压在最上面，必须先取走
推入 push
新元素放到栈顶，旧元素被往下挤
弹出 pop
只能从栈顶拿走一个，下面的看不到
栈顶指针
永远标记'最上面'那个元素的位置
餐厅取餐台对应 →栈

新出锅的餐盘叠在顶上，取餐员只能拿最上面那个

3第 3 页 · 餐厅取餐的类比

PDA的三大组件

控制器居中调度，输入带只读不写，栈提供记忆；三者缺一PDA就无法工作。

图解渲染中…
t1：只读不写，读头只能逐格向右移动c1：有限状态机，综合输入与栈顶决定下一步s1：后进先出栈，是PDA超越FA的记忆来源
4第 4 页 · PDA的三大组件

七元组定义

上页把 PDA 拆成控制、输入、栈三大组件，但每个组件内部还有更具体的元素。下面用七元组 M=(Q,Σ,Γ,δ,q0,Z0,F) 把它们逐项固定下来。

状态集 Q
控制器所有可能状态的有限集合，与 FA 的 Q 同义
输入字母表 Σ
PDA 能读入的输入符号集，与 FA 相同
栈字母表 Γ
推栈允许出现的符号，可包含 Σ 没有的辅助运算符
转移函数 δ
由「状态、当前输入、栈顶符号」三元组驱动，决定下一步动作
起点与终点
q₀ 起始状态，Z₀ 栈底初始符号，F 接受状态集
取餐员岗位手册对应 →PDA 七元组

Q=岗位、Σ=订单字符、Γ=盘子种类、δ=操作规则、q₀/F=起止

$$M=(Q,\Sigma,\Gamma,\delta,q_0,Z_0,F)$$ $$\delta:Q\times(\Sigma\cup\{\varepsilon\})\times\Gamma \to 2^{Q\times\Gamma^*}$$
5第 5 页 · 七元组定义

确定型与不确定型

上一页我们用七元组描述了 PDA 的结构，但它没有规定每一步能有多少选择。补上这条规则，就有了确定型与不确定型之分。

DPDA 的确定性
同一状态、同一输入、同一栈顶，至多一条转移规则
NPDA 的多选择
相同配置下可有多条规则同时适用，需并行尝试
与 FA 的关键区别
FA 中 DFA ≡ NFA；这里 DPDA 真包含于 NPDA，栈让非确定性变强
经典反例 ww^R
偶数长度回文语言只能被 NPDA 识别，任何 DPDA 都做不到
分身术同时探路对应 →NPDA 多分支并行

每个岔口派出分身，对应同一配置下并行尝试多条转移

∣δ(q,a,X)∣≤1 (DPDA),无上界 (NPDA)|\delta(q, a, X)| \leq 1 \text{ (DPDA)}, \quad \text{无上界 (NPDA)}
6第 6 页 · 确定型与不确定型

转移函数详解

δ(q,a,X)的五种情况与符号约定

转移函数详解
δ(q,a,X)的五种情况与符号约定
7第 7 页 · 转移函数详解

即时描述的定义

从前面讲完转移函数，自然问题是『某一步 PDA 到底是什么样』——就像看电影暂停。我们需要一个能完整描述当前瞬间状态的『快照』，叫即时描述。

当前状态 q
PDA 此刻所处的状态，对应七元组 Q 中某个元素
剩余输入 w
还没读完的字符串，下一个待读符号写在最左
栈内容 γ
当前栈里所有符号组成的串，从底到顶记录
栈顶在左
约定串的最左字符是栈顶，新压入的符号向左延伸
电影暂停画面对应 →即时描述(q,w,γ)

画面里演员位置、台词进度、桌上道具，分别对应状态、剩余输入、栈内容

(q, aw, Xα) ⊢ (p, w, βα)(q,\ aw,\ X\alpha)\,\vdash\,(p,\ w,\ \beta\alpha)
8第 8 页 · 即时描述的定义

即时描述的图示

以aabb为例，展示PDA运行中(q,剩余输入,栈)快照的逐拍变化

图解渲染中…
a1：初始：状态q0、剩余输入aabb、栈底标记Za4：读完所有a，进入匹配b阶段，栈顶开始弹Aa6：终态：输入空、栈恢复Z，PDA接受a3：(q,剩余输入,栈)三位一体的完整快照
9第 9 页 · 即时描述的图示

PDA的计算过程

PDA如何接受一个串？答案是：从初始ID出发，沿⊢关系走出一条推导链，直到抵达接受ID。

1
构造初始ID
起始格局 (q₀, w, Z₀)：初始状态、待读输入、栈底符号
2
匹配转移规则
据当前q、输入符a、栈顶X查δ(q,a,X)，ND下可能有多条分支
3
执行转移动作
弹栈顶X、压入新符号串、改状态q→q'，可选消耗输入符a
4
形成推导序列
新ID (q', w', γ') 作为下一步起点，用⊢逐次连接构成推导链⊢*
5
判定接受终止
输入完全耗尽且当前状态q∈F时，序列终止于接受ID
10第 10 页 · PDA的计算过程

空栈接受

上页 PDA 一口口吞完输入串，状态在变、栈在伸缩。现在问：怎么判它『接受』了？两种模式，先讲最干净的那种——空栈接受。

空栈接受的判定
输入读完那一刻栈恰好为空，串被接受
栈底符号 Z₀
预先压入的标记，靠它探测『栈是否真空』
与终态接受对比
盯栈 vs 盯状态，判定准则互不相干
等价定理
空栈可接受 ⇔ 终态可接受 ⇔ CFL
何时选空栈
构造 DPDA、处理歧义文法时更顺手
取餐后托盘清空对应 →空栈接受

托盘全归位=栈清空，订单结清=接受

L(P)={w∣(q0,w,Z0)⊢∗(q,ε,ε)}L(P)=\{w\mid (q_0,w,Z_0)\vdash^*(q,\varepsilon,\varepsilon)\}
11第 11 页 · 空栈接受

终态接受

上一页我们用'栈清空'来判断吃完——可 PDA 还给了另一种判法：只要走到某个指定状态，就算吃完。这就是终态接受。

终态集合 F
七元组中专门指定的接受状态集合
接受条件
存在某次计算使机器进入 F 中任意状态
与空栈的差别
看的是状态，而非栈是否清空
跑到终点线对应 →终态接受

人撞线就赢，手里的东西无关紧要

(q0,w,Z0)⊢∗(q,ε,α), q∈F(q_0, w, Z_0) \vdash^* (q, \varepsilon, \alpha), \ q \in F
12第 12 页 · 终态接受

两种接受方式对比

PDA有两种判定"读完"的方式——看栈空还是看终态。形式不同但能力完全等价，这正是PDA理论的优雅之处。

空栈接受
  • 读完后栈被清空即接受
  • 终态集可为空，仅需起始符Z₀
  • 任意PDA可构造等价终态PDA
终态接受
  • 读完后停在终态集即接受
  • 终态集F非空，栈可留余
  • 任意PDA可构造等价空栈PDA
二者识别能力完全等价（可互转）。写示例PDA时空栈接受更简洁，做构造证明时终态接受更方便，教材多选后者。
13第 13 页 · 两种接受方式对比

PDA语言实例

python

用一段 Python 模拟展示 PDA 识别 {aⁿbⁿ} 的全过程与边界拒绝。

代码高亮加载中…

读 a 压栈记数、读 b 弹栈核销；终态时栈只剩 Z 才接受——这正是 PDA 比 FA 强的关键。

14第 14 页 · PDA语言实例

上下文无关文法回顾

我们用PDA识别了一种语言，但语言本身是怎么被"写"出来的？上下文无关文法（CFG）就是一套造句规则——只要给出有限的产生式，就能系统推出所有合法句子。

V 变元集
可被替换的非终结符号集合
Σ 终结符集
句子中不可再分的原子字符
R 产生式集
核心规则，定义变元如何被替换
S 起始符号
推导的起点，必有产生式涉及
产生式形状 A→α
左部必须为单个变元，正是「上下文无关」的根源
食谱配方对应 →上下文无关文法

食材对应终结符，食材类别对应变元，操作步骤对应产生式

G=(V,Σ,R,S),V∩Σ=∅G = (V, \Sigma, R, S), \quad V \cap \Sigma = \varnothing
15第 15 页 · 上下文无关文法回顾

CFG转PDA

CFG转PDA的核心是：把文法的'推导'变成'栈操作'，每读一个字符就推进一步归约。

1
初始压入S
把开始符号 S 压入空栈，代表'待展开的句型骨架'
2
终结符匹配
栈顶是终结符 a 时，必须读入 a 才能弹出，保证输入与栈同步
3
变量展开
栈顶是变量 A 时，不确定地选一条 A→α，把右部 α 倒序压栈
4
空产生式
若选 A→ε，直接弹出 A，不消耗任何输入字符
5
接受条件
栈空且输入读完时进入接受态，推导完整结束
16第 16 页 · CFG转PDA

PDA转CFG

把PDA的栈操作翻译成CFG的产生式规则，核心是把每一次转移拆成对应文法的推导步。

1
设计非终结符
为每对状态(p,q)和每个栈符X，定义非终结符[pXq]
2
弹栈转移→终结符
若δ(p,a,X)含(q,ε)，加[pXq]→a，读a弹X
3
压栈转移→非终结符链
压栈时把栈符串拆成链：[pXqₖ]→a[qY₁q₁]…[qₖ₋₁Yₖqₖ]
4
钉死起始符
终态接受用[q₀Z₀qf]；空栈接受用[q₀Z₀q]
5
补齐ε-转移
ε-转移把上两式中的a换成ε，不消耗输入
17第 17 页 · PDA转CFG

等价性总结

左：CFG 与 NPDA 等价，共同刻画整个 CFL；中：给 NPDA 加确定限制得到 DPDA；右：DPDA 只覆盖 CFL 的真子集 DCFL。

图解渲染中…
a2：NPDA：不确定型 PDA，每步可有多个可选转移a3：DPDA：每状态-输入-栈顶至多一个转移a4：CFL：上下文无关语言类，等价于 L(CFG)与L(NPDA)a5：DCFL：确定型 CFL，是 CFL 的真子集
18第 18 页 · 等价性总结

核心概念自测

点击作答

关于PDA的终态接受（F接受）和空栈接受（N接受），下列说法正确的是？

19第 19 页 · 核心概念自测

课后思考

先独立思考再看参考答案，试着把每个问题讲给同伴听。

1FA的'记忆'为什么有上限？栈的存储为什么本质上仍然受限？请各给一条直觉或信息论层面的理由。

参考答案FA状态数有限，输入再长也只能维持有限种'上下文'。栈虽然无限，但只能按LIFO访问，底部信息被遮蔽，等价于只能追踪最近一次嵌套外的局部，全局模式天然丢失。

2对同一个PDA，终态接受和空栈接受识别的语言一定相同吗？请举反例或证明。

参考答案不一定。对同一PDA，两种接受方式识别不同语言完全可能。等价定理说的是'存在性等价'：任何PDA都能改造为等价PDA用另一种接受方式，但改造后已不是原来的PDA。

3PDA无法识别哪些语言？试举一类并说明直觉上栈的哪条性质挡在前面。

参考答案典型例子是aⁿbⁿcⁿ（三个等长片段）。直觉上：单个LIFO栈只能同时追踪一段嵌套，无法并行计数'a有几个、b有几个'。这正指向需要图灵机或多栈的能力。

20第 20 页 · 课后思考