下推自动机与CFG化简规范

官官方信息技术老师·10 页·深入（追求细节与边界）·0 次浏览·3 天前
✦ 下推自动机与CFG化简规范信息技术下推自动机与CFG化简规范消除e产生式
PDA构造CFG化简CNF·GNF等价证明

下推自动机与CFG化简规范

看清PDA↔CFG为何等价、化简为何不能跳步、范式为何必须存在

按 空格/→ 演示下一步

1 / 10 页

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

PDA构造CFG化简CNF·GNF等价证明

下推自动机与CFG化简规范

看清PDA↔CFG为何等价、化简为何不能跳步、范式为何必须存在

1第 1 页 · 下推自动机与CFG化简规范

确定下推自动机

上一页的NPDA可以'分身'——同一时刻同时尝试多种走法。但编译器解析代码每步只能看一个选项，不能一边读'if'一边按'for'。DPDA正是把PDA约束成单线程。

唯一转移
任意状态下，每种输入与栈顶组合至多对应一个转移，不允许多选
ε与读入互斥
若某步允许ε转移，则同一栈顶下不能同时定义读字符的转移
真子集关系
DPDA接受的语言类DCFL是CFL的真子集，存在CFL不可被任何DPDA识别
典型应用
编程语言的LR(k)分析器本质就是DPDA，单遍线性时间即可解析
走迷宫不能分身对应 →DPDA

NPDA像同时派多个克隆人试路；DPDA只能选一条走到底

∀q∈Q,a∈Σ∪{ε},X∈Γ: ∣δ(q,a,X)∣≤1\forall q\in Q,a\in\Sigma\cup\{\varepsilon\},X\in\Gamma:\ |\delta(q,a,X)|\leq 1
2第 2 页 · 确定下推自动机

DPDA与其他语言的关系

上页我们已经看到，确定下推自动机在每个“状态、输入、栈顶”组合上至多有一种转移。现在把它放进语言谱系，看看它能识别什么、不能识别什么。

语言谱系位置
DPDA识别的语言构成确定型上下文无关语言DCFL，且DCFL真包含于CFL。
终态与空栈
DPDA可按终态接收，也可规定空栈接收；形式转换时需保留接收时刻。
无歧义性联系
每个DCFL都有无歧义CFG；无歧义CFG语言不一定属于DCFL。
闭包边界
DCFL对补封闭；对并、交、连接和星号等运算均不封闭。
典型应用
适合括号匹配、LR(1)语法等只需确定移进或归约的输入。
单轨分拣机对应 →DPDA

状态是分拣位置，栈是待办标签；每步只能沿一条确定路线走。

3第 3 页 · DPDA与其他语言的关系

终态型DPDA和空栈型DPDA

上一页把DPDA放回了语言谱系，但这台机器'怎么算接受一个串'还没拆开。PDA其实有两条接受路径——就像搬家验收，既可以看'人有没有站在终点牌前'，也可以看'房间有没有真正搬空'。

终态型接受
读完输入后，若DPDA处于指定终态则接受；与DFA的接受方式同源
空栈型接受
读完输入后，若栈恰好为空则接受；无需指定终态
DPDA下不等价
一般PDA两模式可互转；但DPDA下终态型覆盖完整DCFL，空栈型仅覆盖DCFL的一个真子集
编译器的对应
LL(k)自顶向下分析 ↔ 空栈型DPDA；LR(k)自底向上分析 ↔ 终态型DPDA
搬家完工验收对应 →DPDA两种接受

终态型：检查员站在「完成」牌下盖章；空栈型：检查房间是否真已搬空

4第 4 页 · 终态型DPDA和空栈型DPDA

消除无用符号

CFG化简四步走，今天迈第一步——把永远派不上用场的符号扫地出门。

无用符号
无法出现在任何终结符串推导中的符号
生成性
存在推导 X ⇒* w，其中 w 全由终结符组成
可达性
从开始符号 S 出发，能经若干步推导到达
两者缺一不可
只生成不可达、或只可达不生成，都算无用
算法顺序
先去非生成、再去不可达；两顺序结果等价
仓库里的零件对应 →无用符号

零件再贵，如果装不进任何产品，就是仓库里的死库存

Useful(X)  ⟺  Reachable(X)∧Generating(X)\text{Useful}(X) \iff \text{Reachable}(X) \land \text{Generating}(X)
5第 5 页 · 消除无用符号

消除e产生式

化简文法的路上，无用符号清完之后，还剩一类更隐蔽的'隐身'规则——它本身不产生任何字符，却让推导链暗藏分支。这一步要把它们揪出来。

可空变量
若 A 能经多步推导出空串 ε，则 A 为可空（nullable）变量
可空集迭代
基：右部为 ε 的变量；归纳：若 A→X1…Xn 且所有 Xi 可空，则 A 也可空
补全产生式
对每条 A→X1…Xn，新增 A→Y1…Yn，其中 Yi 取 Xi 或 ε（前提 Xi 可空）
删除 ε 产生式
新文法中不再保留任何右部为 ε 的产生式
保留空串语言
若 ε ∈ L(G)，新增起始符 S′→S|ε 单独保留空串
套餐里'可选的小料'对应 →ε产生式消除

小料能不放，那含它的每道菜都补一份'不放它'的版本，穷尽所有组合

A⇒∗ε⇒A∈NULL;A→X1X2⋯Xn,  ∀Xi∈NULL⇒A∈NULLA \Rightarrow^* \varepsilon \Rightarrow A \in \text{NULL};\quad A \to X_1 X_2 \cdots X_n,\; \forall X_i \in \text{NULL} \Rightarrow A \in \text{NULL}
6第 6 页 · 消除e产生式

消除单一产生式

清掉ε产生式和无用符号后，CFG里还藏着一类只改名字、不产字符的产生式。它把推导链拉得很长，却没多走一步实质推导。这就是单一产生式。

什么是单一产生式
形如A→B，左右各一个非终结符，一步推导不增长串长也不产出终结符
消除动机
拉长推导链却不变串内容，妨碍CYK等分析算法，也掩盖真实生成结构
消除算法核心
对每个A求出单元对集合，再把B的所有非单元产生式直接复制一份给A
化简顺序
必须先消ε、再消单元产生式、最后消无用符号，顺序错了可能遗漏合法产生式
部门层层转交任务对应 →单元产生式链A→B→C

A交B再交C才出活，不如让A直接继承C的所有产出能力

unit(A)={B∣A⇒∗B}, 每步均为单元产生式\text{unit}(A) = \{B \mid A \Rightarrow^* B\},\ \text{每步均为单元产生式}
7第 7 页 · 消除单一产生式

CFG的化简与Chomsky范式

经过消除无用符号、ε产生式、单一产生式这三步清洗，CFG 已经干净——但形状还不统一。Chomsky范式把它压成两种标准产生式，让语法形状整齐划一。

CNF定义
产生式只能是 A→BC 或 A→a；A、B、C 为非终结符，a 为终结符
不含ε产生式
前提：CFGG 不能含 ε；CNF 不允许空右部产生式
转换核心步骤
终结符孤立化（引入 X→a），长右部二叉化（引入新非终结符拆链）
语言保持不变
只新增非终结符，原有可派生串仍然全部属于 L(G)
核心用途
为 CYK 等 DP 解析算法提供统一输入，成员性判定可达 O(n³)
标准快递箱对应 →Chomsky范式

物品只能装进「单格箱」(A→a) 或「双格箱」(A→BC)，超大件先拆格再装

P⊆{A→BC∣A,B,C∈V}∪{A→a∣A∈V,a∈T}P \subseteq \{A \to BC \mid A,B,C \in V\} \cup \{A \to a \mid A \in V, a \in T\}
8第 8 页 · CFG的化简与Chomsky范式

本节要点

  • ✓DCFL对补封闭，CFL对补不封闭
  • ✓终态型DPDA能力严格强于空栈型
  • ✓CFG化简顺序固定：先ε后单一再无用
  • ✓Chomsky范式右部至多两个符号
延伸主题：CYK算法与成员判定上下文无关语言的泵引理下推自动机的工程应用
9第 9 页 · 本节要点

课后思考

先独立思考，再对照参考答案——好问题值得多想一会。

1为什么DPDA的终态接受和空栈接受不等价？这暴露出DPDA与NPDA的本质差异在哪？

参考答案DPDA无法兼顾'栈空却未达终态'与'到终态却栈非空'两类遗漏；NPDA凭借非确定性可并行试探两条接受路径，因此两种接受方式对NPDA等价。

2消除无用符号、ε产生式、单一产生式的执行顺序，会影响最终化简结果吗？

参考答案会影响。推荐顺序（先消ε→再消单一→再消无用）每步不引入新问题；颠倒顺序可能在新化简后又冒出新的无用符号或ε产生式。

3Chomsky范式能消除文法的歧义性吗？CNF变换会改变语言的固有歧义吗？

参考答案不能也不会。CNF只重写产生式形态，不触动推导关系。歧义性取决于是否存在两棵不同的语法树，CNF保留树结构，既不消除也不新增歧义。

10第 10 页 · 课后思考
下推自动机与CFG化简规范 · 知识图解