CSCI3130 L04 Part 3 非正则语言

课程：CSCI3130 Formal Languages and Automata Theory · 资料包，学期待核 本讲：L04 Part 3 非正则语言 · 原件 L04-正则语言性质-资料包.pdf（本地课件） p.45–101 定位：从有限状态重复推出泵引理，并逐题检查反证的量词与边界。 前后：上一份 L04-P2-判定问题.md · 下一份 L04-P4-结尾小测.md

p.45 Outline，进入非正则语言证明。

找不到 DFA 并不等于不存在（p.46–48）【新】

p.46 图把有限语言放在正则语言内部，把 $a^nb^n$、偶数长回文放在正则之外。p.47 需要证明任何有限状态数都不够，不是报告自己没画出机器。p.48 引入抽屉原理：有限容器装太多对象，至少一个容器重复使用。接下来把它用于状态访问，而不是把字母表大小当作状态数。

抽屉原理的计数（p.49–51）

p.49–50 四只鸽子进三个洞：若每洞至多一只，总数至多3，与4冲突，故有洞至少两只。p.51 一般化为 n 个对象放入 m 个洞且 n>m。需要严格大于；恰好 m 个对象进 m 个洞时完全可以一一对应。

从鸽子转成状态（p.52–54）

p.52 汇总抽屉原理，p.53 准备把访问时刻对应鸽子、机器状态对应洞。p.54 四状态图中 $q_2$ 同时有 b 自环和指向 $q_3$ 的 b 边；已核对渲染，p.55–57 对应向右边改为 a。以下跑例以 p.55–57 的图为准，不把 p.54 那幅称为已满足确定性的 DFA。

为什么长度四就保证重复（p.55–57）

p.55 图的路径：a 为 $q_1,q_2$；aa 为 $q_1,q_2,q_3$；aab 为 $q_1,q_2,q_3,q_4$，尚无重复。p.56 的 aabb 最后在 $q_4$ 自环，所以重复；bbaa 一开始就重复 $q_1$。短串也可能重复，长度门槛只是保证，不是充要条件。

p.57 写“transitions ... more than the states”；长度恰4只有4次转移，与4状态相等。严谨计数应是包括初态在内的5次状态访问进入4个状态，必有重复。这个计数已按图重算，不改变讲义所需结论。

无穷前缀挤进有限状态（p.58–60）

p.58–59 一般 m 状态 DFA 在读至少 m 位时，前 m 步产生 m+1 次状态访问，故有重复。p.60 用这个思想直接证明 $\{a^nb^n:n\ge0\}$ 非正则。若一台有限机接受它，无穷多个前缀 $a^i$ 中有两个不同长度 n、m 到相同状态 q。接上相同后缀 $b^n$ 后机器行为相同；$a^nb^n$ 应接受，便会错误接受 $a^mb^n$。因 n≠m，后者不在语言中，矛盾。

泵引理从接受路径出发（p.61–63）

p.61 To accept all anbn, an automaton would have to differentiate between all prefixes an and am.

p.61 总结困难是必须区分无限多计数。p.62 假设 L 正则，取一台 m 状态 DFA；p.63 取其语言中一个足够长串 w，路径最后必须到终态。为什么要求 w 属于 L：以后只改路径中间的环，原路径的后半段才有接受保证。

第一次重复决定分割（p.64–66）

p.64 由长度至少 m 得重复状态。p.65 在前 m 步里找第一次重复的状态 q；p.66 把输入切成 x、y、z：x 到第一次 q，y 绕回同一 q，z 从 q 到终态。切分不是凭字符串长相随便挑，它来自假设存在的机器；证明者通常不知道机器，因此也不能控制具体哪一段是 y。

删环与多绕一圈（p.67–69）

p.67 得 $\lvert xy\rvert\le m$ 且 $\lvert y\rvert\ge1$。前者因为第二次 q 出现在前 m 步，后者因为两次访问时刻不同。p.68 删掉环，x 后直接走 z，仍到同一终态。p.69 多走一圈，xyyz 也接受。y 不能空，否则任意串都能选一个毫无作用的“环”，定理就失去约束。

任意非负次重复（p.70–72）

p.70 再多绕一圈得到 xyyyz；p.71–72 总结 $xy^iz\in L$ 对全部整数 i≥0 成立。i=0 是删环，i=1 是原串，i=2 是加一次。每次 y 都回到同一状态，所以无论循环多少次，z 的起点没有改变。

量词顺序就是游戏规则（p.73–75）【新】

p.73 为定理命名；p.74 给出条件，重排为：若无限语言 L 正则，则存在 m≥1，使所有长度至少 m 的 w∈L，都存在分解 w=xyz，满足两条长度限制，并且对所有 i≥0，$xy^iz\in L$。

p.75 的反证游戏按“对方给 m → 我选 w → 对方切 xyz → 我选 i”。证明非正则时，我选的 w 可以依赖 m，选择 i 可以依赖 y；却必须击败每个合法分割。展示一个坏分割不够，因为定理只承诺至少一个好分割。也不能用泵引理证明正则，它是正则性的必要条件。

p.76 Applications 分节页。

将两层“可以依赖”写在纸上（补充）：反证可以整理为

其中 legal 指 $w=xyz$、$\lvert xy\rvert\le m$、$\lvert y\rvert\ge1$，且所选 w 需满足 $\lvert w\rvert\ge m$。先知道 m 再选 w，所以允许指数中出现 m；先看任意 y 的长度 k 再选 i，所以阶乘例允许 i 依赖 k。但你不能先挑自己喜欢的 y 再说“所有分割如此”，也不能用对某一个特定 m 成功来替代所有 m。m 不一定是最小泵长度，更不是输入长度本身。

拿 $a^mb^m$ 作练习，即使 x 空、y 含前 m 个 a，或 x 很长、y 只有一个 a，统一描述 $y=a^k,1\le k\le m$ 都包含它们。这里的长度条件不可省略：$k\ge1$ 保证真的改变数量；$\lvert xy\rvert\le m$ 保证 x、y 都落在前 m 个 a 中，因而 y 不会碰到 b，并推出 $k\le m$。证明中每个长度条件都在承担不同任务。

等量 a、b：选串（p.77–79）

题面（本讲 · Example 4.7 · p.77；公式按讲义重排）

p.77 The language $L=\{a^nb^n:n\ge0\}$ is not regular.

p.78 反设正则，p.79 令 m 为其泵长度，选 $w=a^mb^m$。它确实属于 L，长度2m≥m。把两段都设为 m 的目的，是让前 m 位全部是 a，强迫可泵段不能跨到 b。

任意分割都只改变 a（p.80–82）

p.80 对任何合法 xyz，$y=a^k$，1≤k≤m。p.81 取 i=2；p.82 得 $xy^2z=a^{m+k}b^m$。无需知道 x 多长，只需知道 y 全是 a 且非空。先规定“y就是第一个a”会丢掉对所有分割的论证。

矛盾与回文的选串（p.83–85）

p.83 因 m+k≠m，新串不在 L，与泵引理冲突。

题面（本讲 · Example 4.8 · p.84；公式按讲义重排）

p.84 Show that $L=\{ww^R:w\in\Sigma^{\ast}\}$ is not regular.

本例使用两种不同字母 a、b，适用的字母表至少包含它们；若仅一字母，语言会是偶数长度语言，结论不能照搬。p.85 取见证串 $a^mb^mb^ma^m$，前一半是 $a^mb^m$，后一半确为其反转。

回文两端必须同步（p.86–88）

p.86 任意合法 y 仍为 $a^k$，1≤k≤m，只在最左一段。p.87 取 i=2；p.88 左端变为 m+k 个 a，右端仍 m 个 a，中间有2m个 b。因为中间 b 非空，左右连续 a 段长度不等，串不再回文，故不在该偶数回文语言。

选串失败的原因与严格不等（p.89–91）

p.89 完成回文反证。p.90 若改选纯 a 的 $a^{2m}$，对方可让 y 为偶数长度，每次泵后仍是偶长纯 a 回文，无法保证矛盾。选串要把需要同步的两处隔开。

题面（本讲 · Example 4.9 · p.91；公式按讲义重排）

p.91 Let $\Sigma=\{a,b\}$. The language $L=\{w\in\Sigma^{\ast}:n_a(w)<n_b(w)\}$ is not regular.

取 $a^mb^{m+1}$，任意 y=$a^k$，k≥1，i=2 后 a 有 m+k≥m+1 个，已不再严格少于 b。等号就足以违背严格小于，无须强求 a 更多。

交替块与平方长度（p.92–93）

题面（本讲 · Example 4.10、4.11 · p.92–93；公式按讲义重排）

p.92 Let $\Sigma=\{a,b\}$. The language $L=\{(ab)^na^k:n>k,k\ge0\}$ is not regular.

取讲义的 $(ab)^{m+1}a^m$，y 落在交替前缀内。讲义只列 y=a 或 ab，这不穷尽任意分割；补全为：若删掉的 y 长为奇数，拼接会破坏 ab 的交替，出现开头 b 或内部 aa、bb，且拼接点仍在后续 b 之前，不能藏进末尾纯 a 段。若长为2d，则删后交替块只剩 m+1−d≤m 个，尾端仍 m 个 a，违反 n>k。因此所有分割取 i=0 都失败。

p.93 Let $\Sigma=\{a\}$. The language $L=\{a^n:n\text{ is a perfect square}\}$ is not regular.

取 $a^{m^2}$，y=$a^k$，1≤k≤m。讲义删环得指数 $m^2-k$，对 m≥2 它严格位于 $(m-1)^2$ 与 $m^2$ 间：下界至少 $m^2-m$，比 $(m-1)^2$ 大 m−1。泵长度可增大到至少2，因此论证成立；若不说明这个条件，m=1,k=1 时删后为平方数0。另一种补充处理是 i=2，此时 $m^2<m^2+k<(m+1)^2$ 对全部 m≥1 成立。

两种闭合计数关系（p.94–95）

题面（本讲 · Example 4.12、4.13 · p.94–95；公式按讲义重排）

p.94 Let $\Sigma=\{a,b,c\}$. The language $L=\{a^nb^kc^{n+k}:n\ge0,k\ge0\}$ is not regular.

取 $a^mb^mc^{2m}$，任意 y=$a^t$，1≤t≤m；删掉后 a、b 总数为2m−t，c 数仍2m，条件失败。讲义另用同态 h(a)=a、h(b)=a、h(c)=c，得到 $\{a^rc^r:r\ge0\}$。如果原语言正则，其同态像必正则，和已证非正则矛盾。

p.95 Let $\Sigma=\{a,b\}$. The language $L=\{a^nb^l:n\ne l\}$ is not regular.

取 $a^{m!}b^{(m+1)!}$，其中两指数不同；任意 y=$a^k$，1≤k≤m。因为 k 整除 m!，选

为正整数，泵后 a 指数 $m!+(i-1)k=m!+mm!=(m+1)!$，与 b 相等，离开 L。讲义右上也给封闭性捷径：$\overline L\cap L(a^{\ast}b^{\ast})=\{a^nb^n:n\ge0\}$；交上有序串语言，才能排除补集中杂乱次序的串。

三个常见逻辑错误（p.96–98）

p.96 总列不能用引理证正则、不能从语言外选串、不能自定分割。p.97 强调即使未能泵出语言，也不推出正则。p.98 的素数语言不能直接选 $a^m$，m 未必素数；必须选素数 p≥m，再用 $a^p$。见证串的成员资格是证明的第一道门槛。

素数语言：不用猜 y 的奇偶（p.99–100）

p.99 错误做法是假设 y 的长度为奇数，再希望删后变偶数；对手不必照此切，偶数2本身又是素数。

题面（本讲 · p.100；公式按讲义重排）

p.100 Let $\Sigma=\{a\}$. The language $L=\{a^n:n\text{ is a prime number}\}$ is not regular.

取素数 p≥m，w=$a^p$；任意 y=$a^k$，1≤k≤m，令 i=p+1，泵后长度 $p+(i-1)k=p(k+1)$。两个因子都大于1，所以是合数，无论 k 奇偶均失败。这才覆盖所有分割。

p.101 Questions 结束页；后面小测另列 Part 4。

考试角度：（C 级 通识）常见考法是核对量词、选择有边界的见证串、覆盖全部分割，并说明泵后破坏的究竟是次序还是计数关系。

考试角度：（A 级：HW03-2025T1-题目.pdf Q1，考的是差额不等与带分隔复制的非正则性。）见附录 A1。

考试角度：（A 级：期中练习-含解答-学期待核.pdf Q4(1–3)，对应奇回文、平衡计数与指数间隔；扫描卷题面经视觉读取，练习卷不冒称正式考卷。）见附录 A2。

四状态原例的全部转移与长串（p.55–59）

p.56 列出的 abbabb 依次访问 q1,q2,q2,q2,q3,q4,q4，途中已有重复，而且最终接受。abbbabbabb 依次访问 q1,q2,q2,q2,q2,q3,q4,q4,q3,q4,q4。多个重复点可供选取，但泵引理只需找到其中一段非空闭路，不要求所有重复段都选，也不要求重复发生在终态。

p.74 采用“无限正则语言”的表述，因为接下来要挑任意长见证。更一般的正则泵引理也适用于有限语言：取 m 大于所有成员长度，就没有满足长度门槛的成员，条件空真。于是“无限”不是证明正则性的办法，亦不能把“有限语言没有长串可泵”误判为违反引理。

本讲核心考点

• m 步产生 m+1 次状态访问（p.54–59，C 级）。
• 泵引理的量词与游戏顺序（p.62–75，C 级）。
• 等量、回文及不等式见证串（p.77–92，C 级）。
• 平方、阶乘与素数的指数选择（p.93–100，C 级）。

附录

本部分没有需要另列的推导；定义与算例在相应页段内。

A1 作业/往年题演练（非讲义内容）：差额不等与带分隔复制的非正则性

题面块（HW03-2025T1-题目.pdf（本地课件） · Q1 · p.1；公式按原件重排）：

p.1 (20pts) Prove the following languages are not regular:

p.1 1) $L=\{a^n b^m a^k:k\ne m-n,m\geq n\}$.

p.1 2) $L=\{wcw:w\in\{a,b\}^{\star}\}$.

1）反设正则，泵长p。选 $a^p b^{p+2p!}a^{p!}$，中段减首段为2p!，不等于末段p!，故在L。任何合法分解的非空泵段为aˢ，1≤s≤p。取i=1+p!/s，为整数。首段变p+p!，中段不变，所以m−n=p!恰等于末段；仍满足m≥n，却违反不等条件。对所有分解均有此泵次数，矛盾。自取p=3、s=2，原指数3、15、6，泵i=4后首段9，15−9=6，确实出L。

2）选aᵖcaᵖ，任何合法泵段都在左侧a中，长s≥1。取i=0得到aᵖ⁻ˢcaᵖ，两侧长度不同，不能是同一个w，故出L。分隔c唯一，无法另选一个切口挽救。证明并非对一个特定分解，而覆盖前p格内的全部非空泵段。

回到正文：差额不等与带分隔复制的非正则性

A2 作业/往年题演练（非讲义内容）：奇回文、平衡计数与指数间隔

题面块（期中练习-含解答-学期待核.pdf（本地课件） · Q4 · p.3；公式重排）：

p.3 Prove that the following language is not regular:

p.3 1. $L_A=\{w\in\{a,b\}^{\star}:w\text{ is a palindrome of odd length}\}$.

p.3 2. $L_B=\{w\in\{0,1\}^{\star}:\#0(w)=\#1(w)\}$.

p.3 3. $L_C=\{a^{2^i}:i\geq0\}$.

每题独立反设正则，设泵长p。1取aᵖbaᵖ，合法泵段在左a中，长s≥1，泵2次得aᵖ⁺ˢbaᵖ。唯一b的左右长度不等，不是回文，无论总长是否仍奇都出L。2取0ᵖ1ᵖ，抽掉非空左0段，0数变p−s、1数p，出L。3取长度 $2^{p+1}$，泵段长1≤s≤p，泵2次后长度在 $2^{p+1}$ 与 $2^{p+2}$ 严格之间，因为s<2^{p+1}；它不可能是2的整数幂。所有合法分解都受相同前p格约束，因此三项量词均闭合。

自取p=3说明第3项：见证长16，加1、2、3分别得17、18、19，都夹在16和32之间；正式证明不是只检查这些有限数。

回到正文：奇回文、平衡计数与指数间隔

来源与证据

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

• 原件：L04-正则语言性质-资料包.pdf（本地课件），PDF p.45–101。

• 本次独立学习修订：核对本讲全部103页的文本，视觉复核 p.16–17、21、26、42、54–56、102–103；图示以表格、轨迹和证明展开。