CSCI3130 L04 Part 4 结尾小测

课程：CSCI3130 Formal Languages and Automata Theory · 资料包，学期待核 本讲：L04 Part 4 结尾小测 · 原件 L04-正则语言性质-资料包.pdf（本地课件） p.102–103 定位：完整处理末尾两道泵引理题，并标明原解依赖的边界。 前后：上一份 L04-P3-非正则语言.md

整除与区间约束的小测（p.102–103）

题面（本讲 · Short Quiz (c)、(e) · p.102；图片，视觉读取；公式按原题重排）

p.102 Please use the pumping lemma to show that each of these languages is nonregular:

(c) $L=\{a^nb^l:n/l\text{ is an integer}\}$.

(e) $L=\{a^nb^l:n\le l\le2n\}$.

第(c)问的除法要求 l>0；原页未另写 l 的取值，以下见证的 l 均为正，不涉及除零。p.103 讲义解选 $a^mb^m$ 并删掉 y=$a^k$，称违反整除。已核对原图；若允许 n=0，合法分割 k=m 会产生 $b^m$，比值0仍是整数，因此这一选串未覆盖所有分割。若课程另约定 n≥1，删成 n=0 才可因域限制排除；题页没有明说，不能暗补。

补充：不依赖该歧义的完整证明。 反设正则，取泵长度 m≥1，选 $w=a^{m+1}b^{m+1}$。比例1为整数，长度足够。任意分割受 $\lvert xy\rvert\le m$ 约束，y=$a^k$ 且1≤k≤m，删去后比例

严格在0与1之间，因此不是整数。这次即使 k=m，分子仍为1，所有分割均被排除。

第(e)问按 p.103 选 $a^mb^{m+1}$：m≥1 保证 m≤m+1≤2m。任意 y=$a^k$，1≤k≤m，取 i=3，a 数为 m+2k≥m+2，b 数仍 m+1，于是左侧条件 n≤l 已失败。无需同时破坏 l≤2n。题目两个不等式是“且”，否定其中一个就足够。

考试角度：（C 级 通识）常见考法是审查现成证明是否漏了 k=m、零指数或严格与非严格不等号的边界。

对手最极端的切法也要算进去（补充）

第(c)问的改进不是为了让串更长，而是给可删除前缀留下一位余量。自取 m=3，则见证为 aaaabbbb；合法 y 的长度可能为1、2、3，删除后的比例分别为3/4、2/4、1/4，都严格介于0和1。若仍取 aaabbb，则 y 长3时删成 bbb，比例0是整数，旧论证在这一格失效。用 m+1 保留正分子，正是堵住这一漏洞。

第(e)问也可检查极端 k=1：泵三次相对原串新增两份 y，a 数至少 m+2，已经超过 b 的 m+1。为什么不统一只泵两次？k=1 时 a 数恰为 m+1，与 b 相等，仍满足区间条件，所以 i=2 不保证成功。这里的“三次”是由最小可能泵段长度倒推出来的，不是随意选较大的数字。

将原解的指数变化统一记账（p.103）

对 $w=a^mb^{m+1}$，任意合法切法可记为 $x=a^r,y=a^k,z=a^{m-r-k}b^{m+1}$，其中 r≥0、k≥1、r+k≤m。因此

x 的长度 r 消掉了，说明结论不依赖对手把 y 放在前 m 个 a 的哪个位置。取 i=3 后得到的指数正是 p.103 的 m+2k，这也解释了证明为何覆盖每个位置和每个合法长度。

本讲核心考点

• 整除语言选串要避免泵到零的漏洞（p.102–103，C 级）。
• 区间条件破坏一边即可构成反证（p.102–103，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：无

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

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