CSCI3130 L06 Part 1 文法清理

课程：CSCI3130 Formal Languages and Automata Theory · 资料包，学期待核 本讲：L06 Part 1 文法清理 · 原件 L06-文法变换与范式-资料包.pdf（本地课件） p.1–31 定位：通过等价代入清除空、单位和无用产生式，为标准化做准备。 前后：下一份 L06-P2-乔姆斯基与格雷巴赫范式.md

p.1 标题页；p.2 Outline。

本讲导航

1. P1 文法清理：p.1–31。
2. P2 乔姆斯基与格雷巴赫范式：p.32–52。
3. P3 CYK成员算法：p.53–62。
4. P4 范式小测：p.63–64，Outline 外的尾段。

代入规则为什么保持语言（p.3–4）【新】

p.3 若 $A\to x_1Bx_2$ 且 B 的全部右侧为 $y_1,\ldots,y_n$，可把该 A 规则替成全部 $x_1y_ix_2$。原来两步展开现在合为一步；反过来每条新规则都能恢复成那两步，所以生成的终结串相同。这里要枚举 B 的所有选择，不能只取一个就删除原规则。

题面（本讲 · Example 6.1 · p.4；公式按讲义重排）

p.4 Consider G with following productions

$A\to a\mid aaA\mid abBc,\quad B\to abbA\mid b$.

将 abBc 中的 B 分别代入 abbA、b，得到 $ababbAc$、abbc。因此 A 的规则变成 $A\to a\mid aaA\mid ababbAc\mid abbc$；不是 ababbA，末尾原有 c 必须保留。

部分代入时保留其他路径（p.5–7）

p.5 原文法 $S\to aB,A\to aaA\mid abBc,B\to aA\mid b$，先代 B→b，给 S 加 ab、给 A 加 abbc；原来含 B 的规则仍保留，以便 B 的另一个选择。p.6 再代 B→aA，给 S 加 aaA、给 A 加 abaAc。p.7 抽象为保留 $A\to xBz$ 并加 $A\to xy_1z$。单纯新增这种“捷径”不会引入原来推不出的串；若要删除原路径，必须保证剩余展开全部覆盖。

p.5–6 的删除标记也要读出来：第一轮替入 B→b 后，删除这条 B 规则，但保留 B→aA；第二轮替入它后，B 已无其他出口，所以把 S→aB、A→abBc 两条含 B 的旧入口划掉，最终是 $S\to ab\mid aaA$、$A\to aaA\mid abbc\mid abaAc$。p.7 的抽象式只说明加入一条捷径；“什么时候能删旧边”要连同被代入变量的全部出口检查，不能仅看下方新增式。

p.3 的定理前提还包括 A、B 是不同变量，并只替换所选的那条产生式中指定的 B 出现位置。若右侧有多个 B，应逐位置进行等价变换或一次列全所有组合，不能把不同位置强制选成相同右侧。

可空变量不只是直接空产生式（p.8–10）【新】

p.8 给清理目标：空规则、单位规则、无用变量。p.9 可空指 $A\Rightarrow^{\ast}\lambda$，可以经过多步；直接 $A\to\lambda$ 只是起点。p.10 的 $S\to aMb,M\to aMb\mid\lambda$ 中 M 可空，S 不可空，因为外部 a、b 无法消去。计算可空集合时先收直接空变量，再重复加入右侧全部可空的规则左侧，直到不再新增。

删除可空出现位置（p.11–13）

p.11 删 M→空之前，须给每个 aMb 加一个 ab 版本；所以新文法 $S\to aMb\mid ab,M\to aMb\mid ab$。p.12 同样处理 $S\to aS_1b,S_1\to aS_1b\mid\lambda$，生成的仍是 n≥1 的 $a^nb^n$。

题面（本讲 · Example 6.5 · p.13；公式按讲义重排）

p.13 Find a CFG without λ-productions equivalent to the grammar G:

$S\to ABaC,\quad A\to BC,\quad B\to b\mid\lambda,\quad C\to D\mid\lambda,\quad D\to d$.

B、C 直接可空，A 经 BC 可空。S 的三个可空位置分别留或删，共8个右侧：ABaC、BaC、AaC、ABa、aC、Aa、Ba、a。终结符 a 不可删，所以 S 不可空。A→BC 增加 B、C 两种非空右侧；BC 同时删除得到空串，但此次目标消空，不保留。最终 $A\to BC\mid B\mid C,B\to b,C\to D,D\to d$。新增单位规则下一阶段再处理，不能因它们不好看就直接丢掉。

删的是“出现位置”，不是变量名这个整体（补充自取例）：若 $S\to AA$ 且 $A\to a\mid\lambda$，两个 A 各可留或删，共四种选择：AA、A（删左）、A（删右）、空。去重后是 AA、A、空三种右侧，不能因为变量名只叫 A 就只做一种删法。它们分别覆盖原串 aa、a、空。若目标必须保留空串，就按正文新起点例外处理；不能在某一步默默漏掉它。

可空闭包也需要多轮：自取 $S\to AB,A\to C,C\to\lambda,B\to b$，先得到 C，下一轮才得到 A；S 始终不能加入，因为 B 无法消空。循环 $D\to E,E\to D$ 若没有空出口，不能仅因互相依赖就判可空。这和程序中的循环定义一样，需要一个真正可完成的基础情况。

单位规则只改变名字（p.14–16）【新】

p.14 单位规则为 $A\to B$，右侧恰一个变量；$A\to a$ 是终结规则，不属于它。p.15 $A\to A$ 不输出字符、不改变状态，可立即删。

p.16 示例 $S\to aA,A\to a\mid B,B\to A\mid bb$，A、B 可经单位路径互到。讲义先把 A→B 代进使用 A 的地方，S 加 aB，B 加 B→B；等价性来自每条新路径都有原来两步实现，不是凭空删除单位规则。

处理环并去重（p.17–19）

p.17 删 B→B；p.18 再代 B→A，S 多出重复的 aA。p.19 去重后 $S\to aA\mid aB,A\to a,B\to bb$。开始符号生成 aa 或 abb，和原来一致。这个例子的 A 单独生成语言改变了，但从指定 S 出发的整体语言没变；判断文法等价比较的是 $L(G)$，不是要求每个旧变量的语言都逐个相同。

用单位可达闭包一次处理（p.20–21）

题面（本讲 · Example 6.6 · p.20；公式按讲义重排）

p.20 Remove all unit-productions from

$S\to Aa\mid B,\quad B\to A\mid bb,\quad A\to a\mid bc\mid B$.

图的单位边 S→B、B→A、A→B。S 的闭包为 S、A、B；A、B 的闭包均 A、B。p.21 把闭包里每个变量的非单位规则搬到起点：S 得 Aa、a、bc、bb；A 得 a、bc、bb；B 得 a、bc、bb。单位边全部删除。S→Aa 不属于单位规则，因为右侧还有终结符 a，必须保留。

无用有两种原因（p.22–24）【新】

p.22 A→aA 永远残留 A，没有结束规则，即使从 S 能进入 A 也生成不了终结串。p.23 B→bA 虽可终结，但 S 的推导永远到不了 B，仍无用。p.24 有用要求 A 出现在某次从 S 到完整终结串的成功推导中；“可达”和“能终结”缺一不可。

p.22–25 的三个完整反例为：

• $S\to aSb\mid\lambda\mid A,A\to aA$：走入 A 后没有终结出口，所以删 S→A 和 A→aA。
• $S\to A,A\to aA\mid\lambda,B\to bA$：B 虽能生成 b，却从 S 不可达，所以删 B 的规则。
• $S\to aSb\mid\lambda\mid A,A\to aA,B\to C,C\to D$：A 无法终结；B、C、D 所在链也无终结出口且不从 S 可达，因此相关规则都不贡献语言。

它们共同说明“某规则看起来有字母输出”不够：成功推导必须最终把所有变量消完，并且整个过程确实从开始符号出发。

先删不能终结的变量（p.25–27）

p.25 含无用变量的产生式也不贡献成功推导。

题面（本讲 · Example 6.3 · p.26；公式按讲义重排）

p.26 Eliminate useless symbols and productions from the grammar below:

$S\to aS\mid A\mid C,\quad A\to a,\quad B\to aa,\quad C\to aCb$.

p.27 第一轮 A、B 直接能终结，第二轮 S 经 A 能终结；C 的每个后代还含 C，始终无法加入。所以能终结集合为 A、B、S，删 C 及所有含 C 的规则。

再在剩余文法里查可达（p.28–30）

p.28 剩 $S\to aS\mid A,A\to a,B\to aa$。p.29 从 S 沿变量依赖边可到 A，却到不了 B。p.30 删 B 后只留 S、A。顺序有意义：删掉不能终结的规则可能使原来可达的点失去有效入口，所以应先终结性、后可达性。

清理顺序与空串例外（p.31）

p.31 Step 1: Remove λ-productions

Step 2: Remove unit-productions

Step 3: Remove useless-productions

消空可能新增单位规则，消单位或删除规则可能留下无用变量，故按此顺序收尾。定理明确要求语言不含空串，才能彻底无空产生式。若要保留原语言里的空串，可引入不在右侧出现的新起点 $S_0\to S\mid\lambda$，将它作为标准形式的特许例外；不能一边删所有空规则、一边声称仍生成空串。

考试角度：（C 级 通识）常见考法是完整列可空位置的所有删法，算单位闭包，以及解释为什么必须先终结性再可达性。

考试角度：（A 级：HW03-2025T1-题目.pdf Q5，考的是互相可空变量的清理与语言刻画。）见附录 A1。

本讲核心考点

• 完整代入与部分代入的区别（p.3–7，C 级）。
• 可空集合及出现位置组合（p.9–13，C 级）。
• 单位闭包与去环（p.14–21，C 级）。
• 终结性、可达性与清理顺序（p.22–31，C 级）。

附录

本部分没有需要另列的推导；定义与算例在相应页段内。

A1 作业/往年题演练（非讲义内容）：互相可空变量的清理与语言刻画

题面块（HW03-2025T1-题目.pdf（本地课件） · Q5 · p.1）：

p.1 (20pts) Remove all unit-productions, all useless productions, and all λ-productions from the grammar:

规则S→aAa或bBb；A→C或a；B→C或a；C→CD或λ；D→A或B或ab。

p.1 What language does this grammar generate?

nullable闭包从C开始，加A/B，再加D；S含两端终结符，不可空。消λ后：S→aAa或aa或bBb或bb；A→C或a；B→C或a；C→CD或C或D；D→A或B或ab。C→C是无意义单位自环，可一并消掉。

A/B/C/D在单位可达图中全部互达，因此每个都复制全部非单位出口CD、a、ab。最终S保留前述四条，其余V∈{A,B,C,D}各有V→CD或a或ab。没有空规则、没有单位规则；四变量均可达且能生成a，不是无用变量。允许进一步等价合并时可写E→EE或a或ab，S→aEa或aa或bEb或bb，但这额外合并不是消单位的必要步骤。

刻画语言：原C可以由λ开始，反复接D；D最终贡献a、ab，或进一步经A/B/C产生这些块的拼接。因此C恰生成(a+ab)星，A和B再加的a已在其中。故整体为 $a(a+ab)^{\star}a+b(a+ab)^{\star}b$。去空后的变量生成非空块串，S额外的aa/bb恰补中间为空的两种情况。

检查：aa、bb来自S直接分支；合法例aaba可拆a·ab·a，合法例babb可拆b·ab·b；ab因两端不同不在语言。原C⇒CD⇒D⇒ab，故S⇒aAa⇒aCa⇒aaba，与新规则一致。

回到正文：互相可空变量的清理与语言刻画

来源与证据

历史版本考试证据（本次未重新读取全部试卷）：读了 HW01-2025T1-题目.pdf、HW01-2026T1-题目.pdf、HW02-2025T1-题目-更新.pdf、HW03-2025T1-题目.pdf、HW04-2025T1-题目.pdf、HW05-2025T1-题目.pdf、期中练习-含解答-学期待核.pdf、期末-2022T1-资料包.pdf、Final-Exam-2023T1-题目.pdf、Final-Exam-2024T1-题目.pdf、Final-Exam-2025T1-题目.pdf、期末-2023T1-资料包.pdf、期末-2024未核-资料包.pdf；未识别用途的 PDF：无

• 原件：L06-文法变换与范式-资料包.pdf（本地课件），PDF p.1–31。

• 本次独立学习修订：核对本讲64页文本，视觉复核 p.5–7、20–21、61、63–64；补全删除标记、完整规则与 CYK 正文计算。