CSCI3130 L06 Part 2 乔姆斯基与格雷巴赫范式

课程：CSCI3130 Formal Languages and Automata Theory · 资料包，学期待核本讲：L06 Part 2 乔姆斯基与格雷巴赫范式 · 原件 L06-文法变换与范式-资料包.pdf（本地课件） p.32–52 定位：把一般 CFG 约束成适合证明和解析的两种规则形状。前后：上一份 L06-P1-文法清理.md · 下一份 L06-P3-CYK成员算法.md

p.32 Outline，进入两种标准形式。

CNF 限制的是每条右侧的形状（p.33–35）【新】

p.33 Chomsky Normal Form（CNF）只允许 $A\to BC$ 或 $A\to a$ ：前者恰两个变量，后者恰一个终结符。p.34 二叉分支让推导树的高度和叶子数可以建立关系，便于证明与动态规划。p.35 左文法 $S\to AS\mid a,A\to SA\mid b$ 合法；右文法含 AAS 三变量和 aa 两终结符，均不合法。“右侧两个符号”不等于合格，类型也必须检查。

先隔离终结符（p.36–38）

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

p.36 Convert the grammar with following productions to CNF:

$S\to ABa,\quad A\to aab,\quad B\to Ac$ .

p.37 引入 $T_a\to a,T_b\to b,T_c\to c$ ，把长右侧中的终结符改成对应变量： $S\to ABT_a,A\to T_aT_aT_b,B\to AT_c$ 。替换后都是变量，但 S、A 右侧仍长3，尚不是 CNF。p.38 将 S 的三变量分成 $S\to AV_1,V_1\to BT_a$ 。新变量只负责组合固定后缀，不自行增加选择。

再把长链二叉化（p.39–41）

p.39 对 A 再拆 $A\to T_aV_2,V_2\to T_aT_b$ 。p.40 最终所有规则都合格；原来 S 唯一输出 $aab\cdot aabc\cdot a=aabaabca$ ，新文法逐段还原同一串，变量引入没有改变字母顺序。p.40 的最终八条规则集中抄写如下，供直接按规则推导，不用在三页变换中拼凑：

\begin{aligned} S&\to AV_1,&V_1&\to BT_a,\\ A&\to T_aV_2,&V_2&\to T_aT_b,\\ B&\to AT_c,\\ T_a&\to a,&T_b&\to b,&T_c&\to c. \end{aligned}

例如 $A\Rightarrow T_aV_2\Rightarrow aV_2\Rightarrow aT_aT_b\Rightarrow aaT_b\Rightarrow aab$ ，每次辅助变量只把原固定片段拆开。

p.41 定理说不产生空串的任意 CFG 都有等价 CNF，不表示原文法本来就是 CNF，也不表示转换结果唯一。

通用步骤与一个容易多做的替换（p.42–44）

p.42 先清空规则和单位规则；实践中也清无用符号。p.43 用新 $T_a$ 隔离长右侧内的 a；本来合格的 $A\to a$ 保留即可，若一概改成 $A\to T_a$ ，反而重新造出单位规则。

p.44 对 $A\to C_1\cdots C_n$ ，n≥3，依次设 $A\to C_1V_1,V_1\to C_2V_2,\ldots,V_{n-2}\to C_{n-1}C_n$ 。需要 n−2 个新变量；每个中间变量名称要避免与现有变量碰撞，否则可能串接到别处。

CNF 与 GNF 服务不同目的（p.45–47）【新】

p.45 再次给 CNF 存在定理，p.46 强调其适合解析与定理证明。p.47 Greibach Normal Form（GNF）要求 $A\to aV_1\cdots V_k$ ，k≥0：第一个且唯一一个终结符在最前，其后全是变量。每次最左推导立即产出一个新终结符，所以长度 n 的串有 n 次产生式应用；CNF 则按二叉组合切分。

GNF 例子与两种局部修正（p.48–50）

p.48 的 $S\to cAB,A\to aA\mid bB\mid b,B\to b$ 均合法； $S\to abSb\mid aa$ 在首字母后还有终结符，不合法。

p.49 若 $S\to AB$ 、A 的右侧为 aA、bB、b，则代入 A 得 $S\to aAB\mid bBB\mid bB$ ；A、B 原有规则保留，三种可能一个不能漏。p.50 对 $S\to abSb\mid aa$ ，保留首终结符 a，只把后面的 a、b 换成变量，得 $S\to aT_bST_b\mid aT_a,T_a\to a,T_b\to b$ 。这和 CNF“先全变变量”不同。

存在定理不等于本讲已给通用算法（p.51–52）

p.51 there is an equivalent grammar in Greibach Normal Form

p.51 的条件仍为不产生空串；p.52 说 GNF 有利解析，但一般转换较复杂。本讲两个例子都能局部代入，并没有完整展示如何处理任意左递归文法。学习到这里应会辨认与转换这些例子，不能据此声称所有 CFG 都能仅靠一次替换就变 GNF。

考试角度：（C 级通识）常见考法是逐条判 CNF/GNF 合法性，再给保持输出串次序的转换步骤。

考试角度：（A 级：Final-Exam-2025T1-题目.pdf Q1；期中练习-含解答-学期待核.pdf Q5(4)；Final-Exam-2023T1-题目.pdf Q1；期末-2023T1-资料包.pdf Q1，对应两份文法的CNF完整转换；扫描件视觉读取。）见附录 A1。

为什么 CNF 推导 n 个字恰需 2n−1 步（补充）

考虑非空串、且没有空串特许规则参与的 CNF 推导。每次 $A\to BC$ 让当前变量数增加1；每次 $A\to a$ 让变量数减少1。开始有1个变量，结束有0个变量。若二变量展开用了 b 次、终结展开用了 t 次，就有 $1+b-t=0$ 。每条终结规则恰输出一个字符，故 t=n；于是 b=n−1，总步数 b+t=2n−1。例 CYK 的 aabbb 长5，对应4次二分加5次终结，共9步。

这个计数还解释了两种范式的差别：CNF 把“拆成两块”与“产出字符”分开；GNF 每次最左展开立即贡献一个字符，所以是 n 步。两种都可能描述同一语言，步数不同不代表某个串被改变，也不保证一种文法没有歧义。

自检：A→aB 是 CNF 还是 GNF？

分别检查两种定义要求的符号类型。

展开推理与答案

它符合 GNF：首位终结符 a，后面只有变量 B；不符合 CNF，因为两符号右侧必须都是变量。A→a 同时符合两者；A→BC 只符合 CNF。字数相同不足以判断范式。

本讲核心考点

CNF 的两种合法右侧（p.33–35，C 级）。
终结符隔离与二叉化（p.36–44，C 级）。
GNF 首终结符及后续变量要求（p.47–52，C 级）。

附录

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

A1 作业/往年题演练（非讲义内容）：两份文法的CNF完整转换

题面块（Final-Exam-2025T1-题目.pdf（本地课件） · Q1 · p.2，扫描件视觉读取；期中练习-含解答-学期待核.pdf（本地课件） Q5(4) p.5为同一文法）：

p.2 Convert the grammar:

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

p.2 to Chomsky normal form.

只有A可空。删A→λ并补省略分支，得S→AB或B或aB，A→abb，B→bbA或bb。消单位S→B，把B两出口复制给S，得S→AB或aB或bbA或bb。现在引入Ta→a、Tb→b、X→TbTb；结果：

S→AB 或 TaB 或 XA 或 TbTb。
A→TaX。
B→XA 或 TbTb。
X→TbTb，Ta→a，Tb→b。

每条均两个变量或单个终结符，无λ，因为原语言不含空串；S未在右侧出现。最短bb：原S⇒AB⇒B⇒bb；新S⇒TbTb⇒bTb⇒bb。串abb由S→TaB、B→TbTb；这些例子核对可空补分支没有漏掉。

题面块（Final-Exam-2023T1-题目.pdf（本地课件） · Q1 · p.1；期末-2023T1-资料包.pdf（本地课件）同页同题）：

p.1 Remove all unit-productions, all useless productions, and all λ-productions from the grammar. After that, convert it into the Chomsky Normal Form:

规则S→aA或aBB；A→aaA或λ；B→bB或bbC；C→B。A唯一可空，消空得到S→aA或a或aBB，A→aaA或aa；B原规则不变，C→B。消单位时C复制B的bB和bbC。B/C始终不能生成终结串，连同S→aBB删除，留下S→aA或a，A→aaA或aa。

引入X→a、D→XX。CNF为S→XA或a；A→DA或XX；D→XX；X→a。A生成正偶数个a，S因此生成正奇数个a，与清理前等价。检查a用S→a，aaa用S⇒XA⇒XXX⇒aaa；所有新规则形式合格。

回到正文：两份文法的CNF完整转换

来源与证据

历史版本考试证据（本次未重新读取全部试卷）：读了 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.32–52。
本次独立学习修订：核对本讲64页文本，视觉复核 p.5–7、20–21、61、63–64；补全删除标记、完整规则与 CYK 正文计算。