CSCI3130 T06 · Part 4 计数语言非 CFL

课程：CSCI3130 · 2025T1 本讲：第4部分 / 共5部分 · T06-2025T1.pdf（本地课件） p.9–10 定位：用泵引理在三种字母计数的边界证明非CFL。 前后：上一份 Part 3 · 下一份 Part 5 承接：#L08-01 CFL泵引理、#L08-02 三段等长

本辅导原件只给本题题面，下面的完整转移、推导或反证为学习补充；它们不是原页印出的参考答案。读栈配置时统一把栈顶写在最左，λ边不消耗输入。

在相等边界处选择见证（p.9–10）【已会】

p.9导航，p.10题面。

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

p.10 Show that the language is not context free. $L=\{w\in\{a,b,c\}^{\star}:n_a(w)=n_b(w)\geq n_c(w)\}$

这里不限制字母顺序。反设L为CFL，泵长p，选w=aᵖbᵖcᵖ，它的三种计数均为p，属于L。对任意uvxyz分解，vxy长度≤p且vy非空；该短窗口不可能同时含a和c，因为中间隔着p个b。

令α、β、γ为v和y合计的a、b、c数，三者非负且和正。若α≠β，取i=0，a与b的新计数p−α、p−β不等，出L。若α=β>0，因为窗口含a，所以不能含c，γ=0；取i=0后a=b=p−α<p=c，违反不小于c。最后若α=β=0，则γ>0，取i=2增多c，而a=b仍为p，也出L。三类覆盖所有可能分解，故矛盾。

算一遍（自取p=3说明分支）：若泵段合计各含一个a、一个b，不含c，抽掉后计数(2,2,3)非法；若只含两个c，重复后(3,3,5)非法；若含一b一c，抽掉后(3,2,2)因a≠b非法。数例帮助检查三类，正式证明仍以任意p、任意分解为准。

不能说“L包含aⁿbⁿcⁿ，所以L不是CFL”：CFL可以包含非CFL子集，例如全部串语言。本证明直接让泵后串违背L自己的计数条件。

为什么选不等式恰好取等的边界（补充）

如果见证中 c 很少，抽掉少量 a、b 后仍可能满足 a=b≥c，难以保证出语言。选择三者都是 p，把“≥”放在边界上：只要同时减少 a、b 而不减 c，就马上越界。另一种可能只增加 c，也马上越界。这是见证选择的目的，不能只记住三段等长是常见写法。

短窗口的几何约束则保证三类计数论证成立。任何同时包含一个 a 和一个 c 的连续子串，至少要包含中间全部 p 个 b，故长度至少 p+2；与 $|vxy|\le p$ 矛盾。因此若 α=β>0，确实有 γ=0。这里不需要泵后仍保持 a段、b段、c段的顺序，因为目标语言本来不限制顺序；证明必须违反计数关系，而不能仅说泵后“出现 ba，所以非法”。

本讲核心考点

• 按泵段的三种计数分类，对任意分解找到反例（p.9–10，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：无

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

• 本次独立学习修订：核对对应辅导原件全部文本与本篇题面，保留完整规则、转移与证明。原件12页只有题面与导航，解法明确标为补充。