第 7 章上下文无关语言的性质

文法范式、CFL 泵引理、封闭性与判定问题

Source scope
主要依据教材第 7 章：中文印刷页 177–212，对应 PDF p.190–225/227。目录明确包含无用符号、\(\varepsilon\)-产生式、单位产生式、Chomsky 范式、CFL 泵引理、封闭性与判定性质。

1 0. 本章任务

第 5–6 章回答“CFL 是什么”。本章回答“CFL 有哪些结构性质，以及能算法判断什么”。

2 1. CFG 的范式化

2.1 1.1 去除无用符号

一个变量要真正有用，必须同时满足：

产生性（generating）：它能推导出某个纯终结符串；
可达性（reachable）：从开始符号能推导到包含它的句型。

算法通常先计算产生符号，再从 \(S\) 做可达性传播。

2.2 1.2 去除 \(\varepsilon\)-产生式

\(A\to\varepsilon\) 称为 \(\varepsilon\)-产生式。

先求所有可空变量（nullable variables）：能推导出 \(\varepsilon\) 的变量。

对产生式

\[ A\to X_1X_2\cdots X_k, \]

对其中可空变量选择“保留或删除”，生成必要的新产生式。

若原语言包含 \(\varepsilon\)，通常引入新开始符号 \(S_0\) 保留空串。

2.3 1.3 去除单位产生式

单位产生式形如

\[ A\to B, \]

其中两边都是变量。

先计算单位闭包：若 \(A\Rightarrow^* B\) 只使用单位产生式，则把 \(B\) 的非单位产生式复制给 \(A\)。

2.4 1.4 Chomsky 范式（CNF）

若 \(G\) 为 CNF，则产生式基本形如

\[ A\to BC \]

或

\[ A\to a, \]

必要时允许新开始符号产生 \(\varepsilon\)。

CNF 的价值：

语法树成为二叉树；
可以控制推导树高度与叶子数量；
支撑 CYK 成员性算法；
便于证明 CFL 泵引理。

3 2. CFL 的泵引理

若 \(L\) 是 CFL，则存在泵长度 \(n\)，使任何 \(z\in L\) 且 \(|z|\ge n\) 都能写成

\[ z=uvwxy \]

满足：

\(|vwx|\le n\)；
\(|vx|>0\)；
对所有 \(i\ge0\)， \[uv^iwx^iy\in L.\]

与正则泵引理相比，CFL 同时泵两个片段 \(v\) 和 \(x\)。

3.1 2.1 为什么会出现两个被泵片段

在足够高的 CNF 语法树中，一条根到叶路径上必有某变量重复。上层变量与下层同名变量之间的子树产生两侧上下文，重复这段树结构时，两侧会一起增长，于是得到 \(v\) 与 \(x\)。

3.2 2.2 典型非 CFL：\(\{a^nb^nc^n\}\)

假设是 CFL。取

\[ z=a^nb^nc^n. \]

由于 \(|vwx|\le n\)，短片段 \(vwx\) 不可能同时覆盖完整的三个区域，只能位于一个区域或跨越相邻两个区域。

无论如何，泵 \(v,x\) 都不可能同时保持 \(a,b,c\) 三者数量相等。取 \(i=0\) 或 \(2\) 得到矛盾。

4 3. CFL 的封闭性

CFL 对以下运算封闭：

并；
连接；
Kleene 星；
反转；
同态；
逆同态；
与正则语言求交。

但一般不对以下运算封闭：

交；
补；
差。

4.1 3.1 代入（substitution）

把每个终结符 \(a\) 替换为某个 CFL \(L_a\)，对 CFL 做这种上下文无关代入后仍得到 CFL。很多封闭性可以由代入定理统一推出。

4.2 3.2 与正则语言求交

若 \(L\) 是 CFL，\(R\) 是正则语言，则

\[ L\cap R \]

仍是 CFL。

机器解释：同时运行 PDA 和 DFA，状态取二者乘积；栈仍只由 PDA 管理。

这个性质也是证明语言非 CFL 的强力工具。

5 4. 判定性质

5.1 4.1 CFG/PDA 互转的复杂性

CFG 与 PDA 虽表达能力等价，但构造后的规模可能显著增加。因此算法分析不仅要问“能否转换”，还要关心表示尺寸。

5.2 4.2 CFG 到 CNF 的运行时间

范式化包含：

无用符号消除；
可空变量计算；
单位闭包；
右部二元化。

这些步骤都可以有效完成。

5.3 4.3 空性

判断 \(L(G)=\emptyset\)：只需检查开始符号 \(S\) 是否是产生符号。

5.4 4.4 成员性

给定 CFG \(G\) 与串 \(w\)，可以判定 \(w\in L(G)\)。

CNF 下可使用 CYK 动态规划。

设 \(w=a_1\cdots a_n\)。定义

\[ T[i,j]=\{A\mid A\Rightarrow^* a_i\cdots a_j\}. \]

先处理长度 1，再按区间长度递增，通过产生式 \(A\to BC\) 和所有切分点组合。

最终：

\[ w\in L(G)\iff S\in T[1,n]. \]

典型复杂度为 \(O(n^3|G|)\) 量级。

5.5 4.5 CFL 中的不可判定问题

虽然成员性与空性可判定，但一些更全局的问题不可判定，例如一般 CFG 的：

等价性；
包含关系；
歧义性。

这为第 9 章不可判定性埋下伏笔。

6 5. 证明非 CFL 的策略

优先级建议：

利用与正则语言求交的封闭性把语言过滤成已知非 CFL；
使用逆同态/同态简化结构；
必要时使用 CFL 泵引理。

7 6. 常见错误

CFG 转 CNF 时忘记保留 \(\varepsilon\)；
把“产生变量”与“可达变量”混为一谈；
CFL 泵引理中自己选 \(u,v,w,x,y\)；
误以为 CFL 对交或补封闭；
CYK 中只看相邻切分，而没有枚举所有切分点；
用“PDA 看起来做不到”代替严格非 CFL 证明。

8 7. 关系总结

CFG/PDA
  ↓ normalization
CNF
  ├─ pumping lemma
  ├─ CYK membership
  └─ parse-tree size analysis

CFL closed under union/concat/star/reverse/homomorphism/inverse-homomorphism/intersection-with-regular
CFL not closed under general intersection/complement