CSCI3130 L06 Part 4 范式小测

课程：CSCI3130 Formal Languages and Automata Theory · 资料包，学期待核 本讲：L06 Part 4 范式小测 · 原件 L06-文法变换与范式-资料包.pdf（本地课件） p.63–64 定位：按消空、消单位、隔离终结符、二叉化的顺序完成原讲义小测。 前后：上一份 L06-P3-CYK成员算法.md

从含空规则文法到 CNF（p.63–64）

题面（本讲 · Quiz · p.63；图片，视觉读取；公式按原题重排）

p.63 Convert the grammar

$S\to AB\mid aB,\quad A\to abb\mid\lambda,\quad B\to bbA$

into Chomsky normal form.

先算可空集合：只有 A，B 含不能消去的 bb，S 的两分支都含 B，均不可空。消 A→空时，S→AB 增 S→B，B→bbA 增 B→bb；其余规则保留。因此中间文法 $S\to AB\mid B\mid aB,A\to abb,B\to bbA\mid bb$。

再消单位 S→B，将 B 的两条非单位右侧搬给 S：$S\to AB\mid aB\mid bbA\mid bb$。引入 $V_a\to a,V_b\to b$，并定义 $V_c\to V_bV_b$ 组合 bb、$V_d\to V_aV_b$ 组合 ab。p.64 的最终文法为

名称中的 c、d 只是辅助变量标签，不表示增加了终结符 c、d。每条长右侧现在恰两变量，每条短右侧恰一终结符。原文法 B 生成 bb 或 bbabb，A生成空或abb，故 S 的六个成员为 bb、bbabb、abbbb、abbbbabb、abb、abbabb。新文法四条 S 分支分别覆盖 AB的非空A版本、B的bbabb版本、aB的两版本、B的bb版本，逐个相同；空串仍不属于语言。

考试角度：（C 级 通识）常见考法是检查消空后新增的单位规则是否处理，再逐条检查最终 CNF 的类型。

用六个成员定位是哪一步漏了分支（补充）

原 A 有两种结果：空、abb；原 B 是 bb 后接 A，所以也有两种：bb、bbabb。S→AB 给四种组合：空·bb=bb，空·bbabb=bbabb，abb·bb=abbbb，abb·bbabb=abbbbabb；S→aB 再给 abb、abbabb。这里组合恰好全部不同，所以六个成员无须去重。

若新文法漏 bb 和 bbabb，往往是消 A 可空时没有补 S→B；若只漏 bb，检查 B→bb 是否漏补，或消 S→B 时只复制了 B 的一条出口。若多生成空串，则不应给 S 加空规则：S 每条原分支均含不能消失的 B，原 S 不可空。有限语言在这个例子中能完整列举，因而比只验一个合法串更有诊断力；对无限语言仍需依赖变换的普遍双向对应。

按范式形状逐条验收（p.64）

S 的四个右侧 AB、VcA、VaB、VbVb 都是两个变量；A 的 VdVb、B 的 VcA/VbVb、Vc 的 VbVb、Vd 的 VaVb 也都是两个变量；Va→a、Vb→b 是单终结符。没有单位右侧，没有空右侧，也没有长于两个变量的右侧。因此这里验证的不仅是语言相同，还验证了目标 CNF 的每一条形状约束。

本讲核心考点

• 可空出现引入的单位规则（p.63，C 级）。
• CNF 逐条检查与语言验算（p.64，C 级）。

附录

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

来源与证据

历史版本考试证据（本次未重新读取全部试卷）：读了 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.63–64。

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