CSCI3130 T05 · Part 3 简单文法

课程：CSCI3130 · 2025T1 本讲：第3部分 / 共4部分 · T05-2025T1.pdf（本地课件） p.9–11 定位：简单文法的原题、完整推导与边界核对。 前后：上一份 并语言文法 · 下一份 文法清理 承接：#L05-07 s-grammar

唯一首符号选择与原解的漏洞（p.9–11）【已会】

p.9导航，p.10题面，p.11同页脚8/10追加变换。

题面块（T05 · Problem 3 · PDF p.10；公式按讲义重排）：

p.10 Find a s-grammar for $L=\{a^n b^{2n}:n\geq2\}$.

s-grammar每条规则先出一个终结符，其后只能是变量串；同一左变量与首终结符的组合只能有一条规则。普通CFG S→aSbb或aabbbb虽生成目标，却有同一(S,a)两条候选，也在首符号后留下终结符，不符合要求。

p.11 在最终式前还列了一个中间文法：

它先强制两个 a，再在 B 递归时各增加一个 a、两个 b，最后用 bb 收尾，语言仍正确；但 a 后还有终结符 bb，B→bb 也在首终结符后留 b，尚未满足 s-grammar 格式。这解释了为什么原页还要继续提取终结符。

p.11最终印为S→aAB，A→aCBB，B→b，C→aCCB或b。形式满足s-grammar，但语言不对：C⇒aCCB⇒abCB⇒abaCCBB⇒ababCBB⇒ababbBB⇒ababbbb，于是S可生成前缀aa再接ababbbb再接bbb，出现b之后又有a，超出a段接b段的形状。这是对原文法的反例，不把原解静默改掉。

补充（修正构造）：保留前三条，将C→aCCB改成C→aCBB，另保留C→b。S⇒aaCBBB；若C递归k次再变b，得到a的数量2+k，b的数量3+2k+1=2(2+k)。对每个n≥2取k=n−2都能生成，且单C递归不会产生中途出现a的乱序。

算一遍：n=2，S⇒aAB⇒aaCBBB⇒aabBBB⇒aabbbb；n=3，在C变b前用一次aCBB，得到aaaCBBBBB，再C→b，终结后为aaabbbbbb。每个变量的a/b首标签无冲突，且首标签后全变量，满足simple grammar要求。

在唯一选择之后，还要守住唯一活动的 C（补充）

修正文法的关键不只是把一个字母抄对。由 $S\Rightarrow aaCBBB$ 出发，C 递归 k 次后的句型为 $a^{2+k}CB^{3+2k}$；这个不变量同时记录三件事：只有一个 C，所有 a 已在它左侧，所有待输出的 b 都在它右侧。最后 C→b，再把 B 全变 b，便得到所需数量和次序。原规则 C→aCCB 破坏“只有一个 C”：左侧 C 可以先产 b，右侧 C 后产 a，因而无法维持 a 在 b 前的保证。

检查 s-grammar 形式则是另一张清单：S、A 各只有首符号 a 的一条规则；B 只有首符号 b；C 的两个候选分别以 a、b 开头，不冲突。首个终结符之后均为变量串，允许变量串为空，故 B→b 与 C→b 合法。形式检查和语言不变量证明相互独立，缺任何一项都不能完成本题。

本讲核心考点

• s-grammar形式正确还须核对语言与符号顺序（p.9–11，C 级）。

附录

本Part完整演练的是辅导课原题，推导与原页问题已在正文给出；不新建Tutorial知识条目。

来源与证据

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

• 原件：T05-2025T1.pdf（本地课件），PDF p.9–11。

• 本次独立学习修订：核对对应辅导原件全部文本与本篇题面，保留完整规则、转移与证明。视觉复核物理页5、8、11、14。