CSCI3130 T02 · Part 2 文法构造

课程：CSCI3130 · 2025T1 本讲：第2部分 / 共4部分 · T02-2025T1.pdf（本地课件） p.6–8 定位：把最小长度与偶数约束分别交给初始产生式和递归产生式。 前后：上一份 集合恒等式 · 下一份 奇偶状态 承接：#L01-49 文法、#L01-50 推导、#L01-51 生成语言

从条件拆出基例与增量（p.6–8）【已会】

p.6为Problem 2分节导航；p.7题面，p.8同页脚6/10加解答。

题面块（T02 · Problem 2 · PDF p.7；公式按讲义重排）：

p.7 Find a grammar for the language $L=\{a^n,\text{ where }n\text{ is even and }n>3\}$.

原文法S→aaaaA，A→aAa或λ。S先写四个a，保证最小长度4；A每递归一次增加两个a，最后用λ结束。所以递归k次得到长度4+2k，均满足条件。反向若n为大于3的偶数，则k=(n−4)/2为非负整数，选k次递归就生成目标串；这证明既不多收也不漏收。

算一遍：n=8时，S⇒aaaaA⇒aaaaaAa⇒aaaaaaAaa⇒aaaaaaaa。此处先写两次递归，再把A删去；每次只增加2。n=4直接S⇒aaaaA⇒aaaa。n=6递归一次即可，n=5没有整数k，不能生成。

若题目进一步要求右线性文法，可改为S→aaaaA、A→aaA或λ；若要求每条只出一个终结符，则还需拆辅助变量。本题仅说grammar，没有擅加右线性限制。

完整文法四元组（将原规则所隐含的集合写全）：$G=(\{S,A\},\{a\},\{S\to aaaaA,\ A\to aAa,\ A\to\lambda\},S)$。S、A 是可替换的变量，a 是最终输出字符，λ表示不输出字符。这使题目中的 grammar 不只是一串没有开始符号的规则。

将最短长度与增长步长分别编码（补充）

这里要同时满足三个条件：只有 a、长度为偶数、长度大于3。最小合法长度因此是4。规则 $S\to aaaaA$ 一次固定下界；$A\to aAa$ 每次增加2，保持奇偶性；$A\to\lambda$ 则让构造能在某个有限阶段结束。进行 k 次递归后，句型为 $a^{4+k}Aa^k$，消去 A 后长度为 $4+2k$。这个句型不变量比只列4、6、8三个输出更强：它覆盖任意递归次数。

反过来，对任意合法偶数 n，$k=(n-4)/2$ 是非负整数，故恰好使用 k 次递归就得到它。“k 非负且为整数”分别来自下界和偶数两个条件；两者都要用到。若误把起始规则改成 $S\to aaA$，步长仍正确，却会多生成不合法的 aa，说明保持奇偶性不能代替最短长度约束。

本讲核心考点

• 最小长度4和每次增加2共同刻画全部目标串（p.7–8，C 级）。
• 文法正确性同时证明所有推导合法与所有目标长度可达（p.8，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：无

• 原件：T02-2025T1.pdf（本地课件），PDF p.6–8。

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