CSCI3130 T05 · Part 1 非正则证明

课程：CSCI3130 · 2025T1 本讲：第1部分 / 共4部分 · T05-2025T1.pdf（本地课件） p.1–5 定位：非正则证明的原题、完整推导与边界核对。 前后：上一单元 T02 · 下一份 并语言文法 承接：#L04-07 泵引理、#L04-08 泵引理反证量词

整讲导航：P1 p.1–5、P2 p.6–8、P3 p.9–11、P4 p.12–14。

标题与四题导航（p.1–3）

p.1标题日期为2025年10月16日；p.2总Outline，p.3高亮Problem 1。四题依次为非正则证明、并语言CFG、s-grammar、文法清理。

阶乘为什么能应对所有泵段（p.4–5）【已会】

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

p.4 Prove the language is not regular: $L=\{a^n b^l a^k:k\ne n+l\}$.

p.5选择 $a^{m!}b^{m!}a^{(m+1)!}$。先把泵长增大到m≥2，这不损失泵引理性质，并避免m=1时原选择不在L。因为(m+1)!=(m+1)m!>2m!，原串在L。

任何满足前缀限制的分解xyz，非空y都在第一段a里，写y=aˢ，1≤s≤m。取整数 $i=1+m!(m-1)/s$；s整除m!，所以i是非负整数。泵后首段指数为m!+(i−1)s=m·m!，加中间m!恰为(m+1)!，与末段相等，违反k≠n+l。对所有合法分解都能这样选i，因此与泵引理矛盾。

算一遍（演示取m=3）：原串指数6、6、24。若y长度s=2，取i=7，首段变6+6×2=18，加中段6等于24。若s=1或3，分别取i=13或5，同样得到18；不是只挑一种方便分解。

易错处是先任意规定y长度，或忘记“对每个合法y都能选泵次数”。阶乘专门让1至m的任何s都整除所需增量。

原页没有写 m≥2 的修补；若直接取 m=1，见证为 aba²，恰满足 k=n+l，反而不在题目语言里。正文先增大泵长，随后保持原页的阶乘方法与泵次数，补上的正是这个适用条件。

从要制造的等式倒推泵次数（补充）

本题目标是把“不相等”泵成“相等”。保持中间与末尾段不动，就需要给首段增加 $(m+1)!-m!-m!=m!(m-1)$ 个 a。合法 y 的长度 s 尚未知道，但一定在1至 m 之间；于是应先选择一个被所有这些 s 整除的总增量，再在看到 s 后选择重复次数。阶乘在这里扮演“共同倍数”，并非非正则证明的固定套路。

若最初得到的泵长是 p，取 $m=\max(p,2)$ 的理由也应写清：对长度至少 m 的串，原定理给的分解仍满足 $|xy|\le p\le m$，所以 m 也可作泵长。证明接下来反驳所有 $|xy|\le m$ 的分解，范围甚至更大。m≥2 还保证中间 b 段非空，使三段的边界明确，并保证原串满足严格不等式。

本讲核心考点

• 泵长可增大，阶乘确保任意泵段长度都整除目标增量（p.1–5，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.1–5。

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