CSCI3130 T05 · Part 2 并语言文法

课程：CSCI3130 · 2025T1 本讲：第2部分 / 共4部分 · T05-2025T1.pdf（本地课件） p.6–8 定位：并语言文法的原题、完整推导与边界核对。 前后：上一份 非正则证明 · 下一份 简单文法 承接：#L05-01 上下文无关文法

用两个分支实现“或”（p.6–8）【已会】

p.6导航，p.7题面，p.8同页脚6/10补解答。

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

p.7 Find a context-free grammar for the language $L=\{a^n b^m c^k,\text{ where }n=m\text{ or }m\leq k\}$.

原页最终文法为S→S1C或AS2；S1→aS1b或λ；S2→bS2c或C；A→aA或λ；C→cC或λ。它按“或”分两条生成路线，不需要同一条推导同时满足两个条件。

第一路线S1C：S1每次配一个a、一个b，C接任意c，所以n=m、k任意。第二路线AS2：A给任意a，S2每递归配一个b和一个c，最后内部C再给额外c，因此k≥m。每条规则都维持a、b、c顺序。反过来满足任一条件的目标串，选择对应路线及相应递归次数就能生成。

算一遍：aabbc用S⇒S1C⇒aS1bC⇒aaS1bbC⇒aabbC⇒aabbcC⇒aabbc。abcc用S⇒AS2⇒aAS2⇒aS2⇒abS2c⇒abCc⇒abcCc⇒abcc，属于第二分支。ab也属于第一分支，尽管不满足m≤k；“或”只需一边成立。按非负指数惯例λ也应生成，S1和C均取λ即可。

原页说明段一处把第二子语言仍记L，应理解为L2；不影响最后文法的分支语义。

p.8 的两层记号不能混写：说明段先泛写 S→S1或S2，表示分别选择两个子语言；最终实现则为 S→S1C或AS2，其中 S1 只负责等量 a/b，S2 负责 b/c 配对加额外 c。因此计算具体推导时，应使用最终五组规则，不能遗漏 C 或 A 后仍沿用“整个子语言”的旧含义。

每个分支都给一个参数配方（补充）

对第一分支 $S_1C$，设 S1 递归 r 次、C 输出 t 个 c，终结结果精确为 $a^rb^rc^t$，r、t 独立非负。对第二分支 AS2，设 A 输出 r 个 a，S2 配对递归 s 次，最后 C 输出 t 个额外 c，结果精确为 $a^rb^sc^{s+t}$。这样既能读出不会越界的理由，也能倒求任意目标串的递归次数：满足 n=m 时用 r=n,t=k；满足 m≤k 时用 r=n,s=m,t=k−m。

这里最后的 t≥0 正是第二个不等式给出的条件。不能把 $S_2\to C$ 换成 $S_2\to\lambda$ 而仍声称覆盖 m≤k：那会迫使 t=0，仅剩 m=k，漏掉 abcc。另一方面，两分支可能生成同一个串，这是并集允许的重叠；不要求给每个串指定唯一来源，也不自动承诺这份文法无歧义。

本讲核心考点

• 并语言用开始变量的分支选择；每分支分别证明生成范围（p.6–8，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.6–8。

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