CSCI3130 L08 Part 1 上下文无关泵引理

课程：CSCI3130 Formal Languages and Automata Theory · 资料包，学期待核 本讲：L08 Part 1 上下文无关泵引理 · 原件 L08-上下文无关语言性质-资料包.pdf（本地课件） p.1–136 定位：从推导树的同路径重复推出同步泵两段，并完整分析非 CFL 与非线性例题。 前后：下一份 L08-P2-封闭性与判定.md

p.1 标题页；p.2 Outline；p.3 CFL泵引理分节页。

本讲导航

1. P1 上下文无关泵引理：p.1–136，含线性语言泵引理与本部分小测。
2. P2 封闭性与判定：p.137–178。

推导树里的重复（p.4–6）【新】

p.4 文法 $S\to AB,A\to aBb,B\to Sb\mid b$ 生成无限语言。p.5 给出 $S\Rightarrow AB\Rightarrow aBbB\Rightarrow abbB\Rightarrow abbSb\Rightarrow abbABb\Rightarrow abbaBbBb\Rightarrow abbabbBb\Rightarrow abbabbbb$。p.6 树把这些替换的依赖画出来，叶子从左到右为 abbabbbb。接下来要找的是同一祖先链上的同名变量，而非随便两处相同字母。

一个变量返回自己（p.7–9）

图（p.7）：右侧B子树沿B→S→A→B再遇B。p.8 将旁支先终结，得到 $B\Rightarrow Sb\Rightarrow ABb\Rightarrow aBbBb\Rightarrow aBbbb$。p.9 因此可把这一层看成“B左添a、右添bbb”。关键是两次B具有同一套可用规则，内层B可继续重演外层的结构。

重复两次后的左右变化（p.10–12）

p.10 再对内层B应用同一段，$B\Rightarrow^{\ast}aBbbb\Rightarrow^{\ast}aaBbbbbbb$。p.11 用幂记为 $a^2B(bbb)^2$：左右同时增加，次数相同。p.12 外围已经有 $S\Rightarrow^{\ast}abbB$，这段abb以后保持不动。

零次与一次（p.13–15）

p.13 不套重复层，直接B→b，得abbb。p.14 写成 $abb(a)^0b(bbb)^0$，两侧的零次重复均为空串。p.15 套一层后为abbaBbbb，再令B→b，得abbabbbb。中心b不是被重复的一部分，不能一起加倍。

两次完整结束（p.16–18）

p.16 留两层得到 $abb(a)^2B(bbb)^2$；p.17 内层B终结为b；p.18 确认 $abb(a)^2b(bbb)^2$ 属于语言。长度为3+2+1+6=12，比一次的8多4；增加量来自左边1字母加右边3字母。

第三次套层（p.19–21）

p.19 从两层的未终结B开始；p.20 再包一层得 $abb(a)^3B(bbb)^3$；p.21 令B→b，长度3+3+1+9=16。树越来越深，外围abb与中心b都保持原样。

从算例到一般定理（p.22–24）

p.22 收束三次情形；p.23 对所有i≥0有 $abb(a)^ib(bbb)^i$。p.24 一般证明先去掉空串并清空、单位产生式，以免重复层只变变量名字却不增加任何终结输出。去掉空串不影响找足够长的见证，最后结论仍针对原语言。

讲义的长度界与它尚未证明的内容（p.25–27）

p.25 设p=产生式数×最大右侧长度，再m=p+1，例中4×3=12、m=13。p.26 要说明长串推导必有变量重复；p.27 把推导排成一串句型。核对说明：这个计数能逼某规则在整个推导中重复，却不能保证重复点在同一祖先路径上。只有后者才能把内层子树换进外层；两棵兄弟子树中的相同变量并不能直接泵。原页已视觉核对，安全的通用泵长度由CNF树高给出，见附录 A1。

总步数不能替代路径深度（p.28–30）

p.28 以每步最大增长f估计推导总步数，p.29 推出步数超过规则数，p.30 使用抽屉原理得到某规则重复。到这里“有重复规则”成立，但还欠祖先关系；不能凭两次出现A就写 $A\Rightarrow^{\ast}vAy$。例如两侧独立的A都展开a，也重复规则，却没有A递归包含A。附录的CNF论证明确选一条最长根叶路径补上这一步。

五段来自一棵树的两个同名节点（p.31–33）

p.31 总结重复，p.32 图将外层A以外分为u、z，两层A之间左右旁支输出分为v、y，内层A输出为x。p.33 三段推导为 $S\Rightarrow^{\ast}uAz$、$A\Rightarrow^{\ast}vAy$、$A\Rightarrow^{\ast}x$。所以原串 w=uvxyz。v和y可能一个为空，但不能都空；u、z只是外围，不参与重复。

删除一层和多套一层（p.34–36）

p.34 直接将外层A用内层的A→x推导替换，得uxz；p.35 套一次得uvxyz；p.36 套两次得uvvxyyz。右侧y在两层外围依次出现，字符串结果是y的同次幂，不是把y反转。

任意重复次数（p.37–39）

p.37 套三次得uvvvxyyyz，p.38 给i层推导，p.39 得所有 $uv^ixy^iz$ 都由文法生成。两处指数必须相同；这个同步性来自一次替换同时增长左右两边，并非允许分别任取次数。

两条长度限制的来源（p.40–42）

p.40 将去空串后的语言包含回原L。p.41 要 $\lvert vxy\rvert\le m$，严格来源是选择足够靠近叶子的重复A，使外层子树高度受变量数控制，详见附录；不是只说“最后重复”就自动得到p.25的线性数值界。p.42 $\lvert vy\rvert\ge1$，因为两层A之间至少有一次二叉展开，其旁支在无空产生式文法中贡献非空终结串。

将课件缺少的同路径长度界补完整（p.25–42）

先取生成 $L\setminus\{\lambda\}$ 的CNF文法，设变量数为k，取m=$2^k$。CNF每个变量要么分成两个变量，要么输出一个终结符。若任一根叶路径最多经过k个变量，终结叶子数至多 $2^{k-1}$；因此长度至少 $2^k$ 的串，树上必有路径经过至少k+1个变量。

取一条最长根叶路径，在最靠近叶子的k+1个变量节点中，抽屉原理保证两个同名A。它们确为祖先与后代。较高A的子树高度至多k次二分，因此其叶子数、即vxy长度至多 $2^k=m$。两A之间至少有一条二叉规则，旁支在无空规则文法中生成非空串，所以vy至少一字母。以较低A子树替较高A子树可删一层；反复嵌入两A之间的树段可加任意层，得到全部 $uv^ixy^iz$。

CFL 泵引理的完整条件（p.43）

p.43 For infinite context-free language L there exists an integer m such that

定理余下内容按讲义重排：每个w∈L且 $\lvert w\rvert\ge m$，存在w=uvxyz，满足 $\lvert vxy\rvert\le m$、$\lvert vy\rvert\ge1$，并对全部整数i≥0有 $uv^ixy^iz\in L$。反证仍是“对方给m—我选w—对方切五段—我选i”；不能指定v和y恰是自己想要的位置。与正则引理不同，受限的是中间窗口，不是必须位于整个串的开头。

p.44 Applications分节页。

把五段放在同一条时间线上看（补充）：u 和 z 是整棵外层子树之外的固定前后缀，x 是较低重复变量最终生成的中心串，v/y 才是两层之间新增的两翼。泵零次得到 uxz，不是删掉整个 vxy；泵两次得到 uvvxyyz，不是将 vxy 整块复制。用本讲最早的例子，u=abb、v=a、x=b、y=bbb、z为空，原串长8；泵零次长4，泵两次长12，每次变化为 $\lvert v\rvert+\lvert y\rvert=4$。中心 b 每种情况下都恰保留一次。

正则泵段被迫位于前 m 格，CFL 的窗口 vxy 却可落在整串任何位置，因此只分析“开头全是 a”远远不够。可以借窗口长度限制减少分类，但必须先证明哪些位置不可能，例如跨过整段 b 同时接触 a/c 至少要 m+2 格。这种“先排除不可能布局，再处理所有剩余布局”的顺序，避免对手把泵段放在未讨论之处。

三段等量语言的选串（p.45–47）

p.45 放出新的非CFL例。

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

p.46 The language $L=\{a^nb^nc^n:n\ge0\}$ is not context free.

p.47 反设为CFL，取其泵长度。目标是证明有限窗口不能同时同步修改三段计数；只证明“这台PDA做不到”还不够。

长度 m 的窗口放在哪里（p.48–50）

p.48 选 $a^mb^mc^m$，属于L、长3m。p.49 任意分割须满足窗口长≤m，两泵段合计非空；p.50 引理要求所有i均留在L。由于整个b段已长m，窗口若同时含a与c至少长m+2，所以最多碰两类字母。

窗口完全位于 a 段（p.51–53）

p.51 开始穷尽位置；p.52–53 第一类窗口全在a段，v、y均为a串，合计k≥1。u和z可含其他字母，但泵操作不会改它们，故b、c计数固定m。

第一类的矛盾（p.54–56）

p.54 取i=2，a变m+k；p.55 这是引理声称应接受的串；p.56 实际计数(m+k,m,m)不全等，故不在L。k无须确定，只用k≥1便够。

窗口在 b 或 c 内（p.57–59）

p.57–58 第二类全在b，令k为v、y总长，泵两次得到(m,m+k,m)，a、c不变，b变多。p.59 第三类全在c，下一页完成同样的计数检查。这里不把“类似”当作完成了证明，明确指出哪一计数改变。

c 内与跨 a/b 边界（p.60–62）

p.60 第三类泵两次计数(m,m,m+k)，违反相等。p.61 第四类窗口跨a/b；p.62 先看v只含a、y只含b，分别长k1、k2，允许其中一个零但总和≥1。c一位都不改。

两种计数一起变也不够（p.63–65）

p.63 得(m+k1,m+k2,m)。p.64 即使k1=k2，两者仍与未动的c不同；p.65 若其中一个零，另一个仍变多，所以全部合法分割都失败。

某个泵段本身跨边界（p.66–68）

p.66 若v含a和b，写v=$a^{r}b^{s}$，r,s≥1；p.67 重复v出现 $a^rb^sa^rb^s$，中间b后又有a，破坏 $a^{\ast}b^{\ast}c^{\ast}$ 次序；p.68 引理却要求该串在L，矛盾不必再依赖精确计数。

y 跨边界也要展开（p.69–71）

p.69 完成v混合的反证。p.70 若y=$a^rb^s$且r,s≥1，p.71 重复y同样出现b后再a，无论v是否为空都非法。v、y是互不重叠的子串，单个a/b边界不可能同时落在两者内部。

跨 b/c 边界与覆盖完整性（p.72–74）

p.72–73 第五类跨b/c：若两个泵段各只含一种字母，b或c增加而a固定m；若某段含b后c，其复制会形成c后b，破坏顺序。两种情况都出L。p.74 由窗口≤m排除跨两条边界，至此全覆盖。

从三段匹配到复制串（p.75–77）

p.75 完成非CFL结论；p.76 提醒栈适合反向匹配，但不自动支持同向复制。

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

p.77 The language $L=\{vv:v\in\{a,b\}^{\ast}\}$ is not context free.

这里语言定义的v与泵分割中的v同名但角色不同；下文“复制半串”与“泵段v”分开称呼，避免偷换。

复制串的四个连续块（p.78–80）

p.78 反设CFL；p.79 选 $a^mb^ma^mb^m$，两半均为 $a^mb^m$。p.80 任意五段分割仍只有长度m的局部窗口。下面用i=2，四个原块都不会被删空，有利于按连续同字母块判断复制结构。

只改变第一个 a 块（p.81–83）

p.81 检查窗口位置；p.82 v、y全在第一个a块，合计k≥1；p.83 泵后四块长度(m+k,m,m,m)。若一个以a开始、以b结束且只有四个交替块的串是两个相同半串，其每半必恰两个块，故第一第三、第二第四的长度必须分别相等。

第一与第三块不再一样（p.84–86）

p.84–85 第一块m+k与第三块m不同，故不可能是复制串；不能只是按旧中点切一次失败就下结论，应使用刚才的块结构判据。p.86 第二类v在首a块、y在首b块，计数增量为k1、k2，总和非零。

第一半改变、第二半固定（p.87–89）

p.87 四块长度(m+k1,m+k2,m,m)；p.88 至少一对对应块不等；p.89 与引理矛盾。即便串的中点位置因长度改变而移动，四块判据仍排除了任何合法重新切半，不依赖旧中点。

泵段跨 a/b 会产生六块（p.90–92）

p.90 v=$a^{k1}b^{k2}$且两指数正；p.91 复制v在原四块中多产生a、b两块，成为六个正长度交替块。p.92 为什么六块不可能是平方串：全串以a开始、以b结束，若为tt，则t也以a开始、以b结束，t的块数必为偶数；连接处b接a不合并，因此tt块数是4的倍数。6不是4的倍数，故不在L。

换 y 跨边界及其他单块（p.93–95）

p.93 完成跨界v情况；原页局部指数标注有省略，判断采用块数，不依赖那一行的缩写。p.94 若y跨首a/b，复制y同样产生六块。p.95 窗口单独在第二、第三、第四块，则只有该块增长，另一对应块固定m，分别违反第二=第四、第三=第一、第四=第二。

中间边界和末边界（p.96–98）

p.96 跨第二b/第三a，若泵段纯字母，则只改相邻块2、3，块4、1分别固定，至少一个对应关系失败；若一段混合，则仍新增两块成六块。跨第三a/第四b也一样，但明确对应的是块3对1、块4对2。p.97 窗口不能跨越整块再到非相邻块，因为中间块已长m。p.98 所有窗口类型均排除，复制语言非CFL。

阶乘长度的空隙（p.99–101）

p.99 加入一元语言例。

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

p.100 The language $L=\{a^{n!}:n\ge0\}$ is not context free.

p.101 反设CFL。只有一个字母时不用分析位置，只要控制泵后总长度落在两个相邻阶乘之间。

阶乘例的见证与所有分割（p.102–104）

p.102 选 $a^{m!}$，把泵长度增大到至少2；p.103 任意分割仍满足窗口界；p.104 所有v、y只能由a组成。不能要求两段都非空，引理只要求合计非空。

泵后长度增加多少（p.105–107）

p.105 设v长k1、y长k2，1≤k1+k2≤m；p.106 取i=2，长度m!+k1+k2；p.107 合并记k，1≤k≤m。u、x、z总长度保持原样，所以增加量只有k，而不是2k。

夹在相邻阶乘之间（p.108–110）

p.108 得新串 $a^{m!+k}$。p.109 对m≥2，$m!<m!+k\le m!+m<m!+m\cdot m!=(m+1)!$。p.110 相邻阶乘之间没有另一阶乘，故泵后串不在语言。m=2时也有效：新长在3到4，下一阶乘为6。

结论与非线性计数关系（p.111–113）

p.111 引理要求成员而算得非成员，p.112 得非CFL。p.113 下一例要求a的个数为b个数的平方；这不是栈简单一对一的线性配对。

平方关系选边界串（p.114–116）

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

p.114 The language $L=\{a^{n^2}b^n:n\ge0\}$ is not context free.

p.115 反设CFL；p.116 取 $a^{m^2}b^m$。任意合法泵段合计长度至多m，修改a个数的幅度线性受限，但修改b之后要求的平方值变化更大。

把最复杂情形单列（p.117–119）

p.117–118 任意分割并分类，p.119 先看v全a、y全b。其他可能是都落一个块、或一个泵段混合跨界，后文也必须处理，不能假定这种布局总发生。

删除两边的计数（p.120–122）

p.120 令v=$a^{k1}$、y=$b^{k2}$，1≤k1+k2≤m；p.121 先取两者皆正；p.122 取i=0，剩 $a^{m^2-k1}b^{m-k2}$。合法关系若继续成立，必须有 $m^2-k1=(m-k2)^2$。

平方差给严格矛盾（p.123–125）

p.123 写出被删后的串；p.124 因k2≥1且k1≤m−1，$(m-k2)^2\le(m-1)^2=m^2-2m+1<m^2-k1$。最后严格差至少m，故不会相等。p.125 新串不在语言。

把其余分割补齐（p.126–128）

p.126 完成两段均非空情形。p.127 剩余情况：若只改a，i=0改变a数但b数仍m，平方关系失败；若只改b，i=0改变b数而a数仍m²，仍失败；若某泵段同时含a和b，i=2制造b后再a，破坏语言顺序。v、y全在同一字母块也属于“只改一种”；两者之一空同样已覆盖。p.128 因而整体反证完成。

线性语言的更强局部限制（p.129–131）【新】

p.129 线性语言指存在某份线性CFG生成它；给出一份非线性文法不能证明语言非线性。p.130 线性语言泵引理仍泵v和y，但长度限制变成 $\lvert uvyz\rvert\le m$，即两端外侧的总量受限，中心x可长。与普通CFL引理的 $\lvert vxy\rvert\le m$ 完全不同，不能混用。

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

p.131 Show the following language $L=\{w:n_a(w)=n_b(w)\}$ is not linear.

选 $a^mb^{2m}a^m$。因为uv和yz分别在两端且合计长≤m，它们都碰不到中间b；特别v、y只能是a串，合计k≥1。i=2后a总数2m+k，b仍2m，离开L。原页把uv、yz的长度用到泵后指数里，严格增加量应只算v、y，u、z不重复；这不影响修正后的反证。

p.130 的线性版本为何限制两端：线性规则右侧至多一个变量，因此一条推导只有一条尚未完成的变量链，不会像一般 CFG 那样分成两棵含变量的子树。先去掉无用变量并将单位规则消除，对足够长的串，沿这条链找靠近起点的一对同名变量。进入外层变量前已输出的两端为 u、z，两次出现之间输出 v、y，剩余核心为 x。有限变量数和单步最大输出长度给 $|uvyz|$ 一个统一常数界；核心 x 不受这个近起点界限制。重复两次变量之间的链仍同步增加 v、y。这解释了课件为什么换了长度条件，而不是把 CFL 版本的字母顺序随便改写。

p.129、131 对等量任意次序语言给出的完整 CFG 是 $S\to SS\mid\lambda\mid aSb\mid bSa$。它是 CFL 的正面证据；随后用线性泵引理排除所有线性 CFG，才能得出“CFL 但非线性”的分类。

本部分四道小测（p.132–133）

题面（本讲 · Quiz · p.132；图片，视觉读取；公式按原题重排）

p.132 Use the pumping lemma to prove that the following languages are not context-free.

(a) $L=\{a^n:n\text{ is prime}\}$ (A prime number is divided only by itself and 1.)

(b) $L=\{a^nb^j:n\le j^2\}$

(c) $L=\{a^nb^jc^k:k=jn\}$

(d) $L=\{w:n_a(w)<n_b(w)<n_c(w)\}$

p.133 解(a)：取素数p≥m，w=$a^p$。任意v、y总长k≥1，取i=p+1，泵后长度p+pk=p(k+1)，两个因子均大于1，合数，矛盾。原页中间公式与最终指数有笔误，已按“原长加(i−1)倍泵段长度”重算，不能漏掉原来的p。

小测平方上界（p.134）

第(b)题选 $a^{m^2}b^m$，恰在上界。令v、y合计含α个a、β个b，1≤α+β≤m。若β=0，取i=2，a数变m²+α而b仍m，超过平方上界。若β>0，取i=0，顺序仍a后b，a数m²−α、b数m−β；由于α≤m−β，

更直观：β≥1使 $(m-\beta)^2\le(m-1)^2$，而α≤m−1使 $m^2-\alpha\ge m^2-m+1>(m-1)^2$。故仍超过上界。原解说仅改a时删环也出语言，实际删除a会继续满足“≤”；此分支应泵上而非泵下。

小测乘积关系（p.135）

第(c)题选 $a^mb^mc^{m^2}$。长度≤m的窗口不能同时接触a和c。令泵段的三字母计数为α、β、γ。若γ=0，至少α或β正，取i=2，要求的乘积 $(m+\alpha)(m+\beta)>m^2$，c却不变，失败；混合段造成乱序只会更早失败。若γ>0，则α=0。若β=0，只改c便失败；若β>0，取i=0，要求c数m(m−β)，实际m²−γ，而mβ≥m>γ（因为β+γ≤m且β>0），二者不同。这样覆盖原页只展示的b/c双改情形以外的全部分割。

小测严格递增的计数（p.136）

第(d)题按原页选 $b^{m+1}a^mc^{m+2}$，a、b、c计数为m、m+1、m+2。窗口长≤m，不能同时碰b和c，因为中间a块已长m。若泵段不含c，取i=2：若含b，b数至少m+2，不再小于c；若不含b，则含a，a数至少m+1，不再小于b。若泵段含c，则不含b，取i=0，c数至多m+1，与未变的b数相比不再严格大。两类覆盖所有分割，证明完成；此语言不限制字母顺序，所以不能把泵出乱序当作理由。

考试角度：（C 级 通识）常见考法是区分两个泵引理的窗口，穷尽泵段位置，并为不同分割选择不同的泵指数。

考试角度：（A 级：HW04-2025T1-题目.pdf Q4，对应计数语言非CFL。）见附录 A2。

考试角度：（A 级：期末-2022T1-资料包.pdf Q4；Final-Exam-2023T1-题目.pdf Q6；期末-2023T1-资料包.pdf Q6；Final-Exam-2024T1-题目.pdf Q4；期末-2024未核-资料包.pdf Q4，对应对称三段与严格不等式的非CFL证明；扫描件视觉读取，原题印刷问题在附录注明。）见附录 A3。

考试角度：（A 级：Final-Exam-2025T1-题目.pdf Q3(a–b)，对应平方计数与素数长度；扫描件视觉读取，原题印刷问题在附录注明。）见附录 A4。

本讲核心考点

• 五段分解与同步指数（p.32–43，C 级）。
• 三段等量、复制、阶乘及平方关系（p.46–128，C 级）。
• 线性语言的两端长度界（p.129–131，C 级）。
• 所有分割的分类与泵指数选择（p.132–136，C 级）。

附录

A1 用 CNF 补全泵引理的树高论证

先取生成 $L\setminus\{\lambda\}$ 的CNF文法，设变量数为k，取m=$2^k$。CNF每个变量要么分成两个变量，要么输出一个终结符。若任一根叶路径最多经过k个变量，终结叶子数至多 $2^{k-1}$；因此长度至少 $2^k$ 的串，树上必有路径经过至少k+1个变量。

取一条最长根叶路径，在最靠近叶子的k+1个变量节点中，抽屉原理保证两个同名A。它们确为祖先与后代。较高A的子树高度至多k次二分，因此其叶子数、即vxy长度至多 $2^k=m$。两A之间至少有一条二叉规则，旁支在无空规则文法中生成非空串，所以vy至少一字母。以较低A子树替较高A子树可删一层；反复嵌入两A之间的树段可加任意层，得到全部 $uv^ixy^iz$。

原页p.25的线性界并非一般安全界。补充反例（非讲义内容，自取文法）：$S\to BB\mid bS,B\to CC,C\to DD,D\to EE,E\to FF,F\to aa$，无空或单位规则，共7条、最大右侧长2，原公式给m=15。它的语言为 $\{b^ra^{64}:r\ge0\}$，串 $a^{64}$ 长度大于15，却不能泵任何非空a段而仍保持a恰64个。树中的规则在兄弟支大量重复，不代表同一路径变量重复。这个反例只用于说明原证明界的缺口，不入课程记忆条目。

回到正文

A2 作业/往年题演练（非讲义内容）：HW04-2025T1-题目.pdf Q4

题面块（HW04-2025T1-题目.pdf（本地课件） · Q4 · PDF p.1；与该辅导原题一致）：

p.1 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自己的计数条件。

回到正文：HW04-2025T1-题目.pdf Q4

A3 作业/往年题演练（非讲义内容）：对称三段与严格不等式的非CFL证明

题面块（期末-2022T1-资料包.pdf（本地课件） · Q4 · p.3，扫描件视觉读取）：

p.3 Prove that the following language is not context-free. $L=\{w\in\{a,b\}^{\star}:w\text{ is a palindrome with an equal number of a's and b's}\}$.

p.3 Recall that a palindrome reads the same forward and backward.

反设CFL，泵长p，取aᵖb²ᵖaᵖ，既回文又两字母各2p。任意uvxyz的窗口vxy长度≤p，不可能同时触及左右两段a。取i=0删除v/y。若删除任何a，只能改变一侧a段，另一侧保持p，且中间b仍至少p个，因此不再回文；若未删a，则至少删一个b，a数仍2p而b更少，计数不等。每种合法分解都失败，故非CFL。

题面块（Final-Exam-2023T1-题目.pdf（本地课件） · Q6(a) · p.2；期末-2023T1-资料包.pdf（本地课件）同题；Final-Exam-2024T1-题目.pdf（本地课件） Q4(2) p.1、期末-2024未核-资料包.pdf（本地课件）同题）：

p.2 Use the pumping lemma to prove the following languages are not context-free: (a) $L=\{a^n b^{2n}a^n\}$.

同样取aᵖb²ᵖaᵖ并泵0。若删除一侧a，两端指数不再相等；若只删b，两端仍p但中间不再2p。删除保持三段次序，且两端不会同时改，所有分解穷尽，因此非CFL。2024题行同时出现“prove ... not context-free”和“Determine whether ... context free”的重复指令，数学对象按清晰的两条语言分别判断，结论不靠标题预设。

题面块（2023两文件 · Q6(b) · p.2）：

p.2 (b) $L=\{0^a1^b2^c\text{ with }a<b<c\}$

取0ᵖ1ᵖ⁺¹2ᵖ⁺²。设v/y中三种符号数量α、β、γ，和正；窗口不可能同时含0和2。若β>0且γ=0，泵2次后b至少p+2，而c仍p+2，破坏b<c。若β>0且γ>0，则α=0，泵0后b≤p而a=p，破坏a<b。若β=0、α>0，γ=0，泵2后a≥p+1=b，失败。最后β=α=0、γ>0，泵0后c≤p+1=b，也失败。若泵导致段序不正确，更已出L，不需另行补救。这四类包含全部情况。

题面块（2024两文件 · Q4(1) · p.1）：

p.1 1) $L=\{a^n b^j c^k:n<j,n\leq k\leq j\}$

取aᵖbᵖ⁺¹cᵖ，在边界n=k=p、j=p+1上。窗口长度≤p，不能同时触及a和c。若泵段含a，泵2使n>k；若不含a却含c，泵0使k<n；若两者均不含，只含至少一个b，泵0使j≤n。每类都违反一条明确约束，故非CFL。注意选普通aᵖbᵖcᵖ不在原语言，因为n<j是严格的；见证必须先合法。

回到正文：对称三段与严格不等式的非CFL证明

A4 作业/往年题演练（非讲义内容）：平方计数与素数长度

题面块（Final-Exam-2025T1-题目.pdf（本地课件） · Q3 · p.2，扫描件视觉读取；公式按原图重排）：

p.2 Use the pumping lemma to prove the following languages are not context-free:

p.2 (a) [10 points] $L=\{a^n b^j:n=j^2\}$

p.2 (b) [10 points] $L=\{a^p n>0,p\text{ is a prime number}\}$ (p is a prime number iff p can not be divided by any positive integer not equal to 1)

(b)原式在aᵖ后混入n>0且缺分隔，括号内素数定义也漏掉“自身”这个允许因子。若把括号逐字当定义，每个正整数都可被自身整除，无法得到通常的素数语言。以下按题目明确写出的“prime number”通常含义，即p>1且正因子仅1与p，解释其预期问题；不把印刷错误作为定理入库。

(a)反设CFL，泵长P，选a的数量P²、b的数量P。任意合法v/y合计a数α、b数β，0<α+β≤P。泵2后计数P²+α、P+β。若β=0，α>0，a数改变而b平方不变，失配；若β≥1，则b平方至少P²+2P+1，而a数至多P²+P，仍失配。如果泵后段序乱了，也当然不在L。两种情况覆盖全部分解，故非CFL。

(b)取素数q≥P，存在任意大的素数。见证aᵠ；任意合法泵段总长d，1≤d≤P。取泵次数i=q+1，长度变q+qd=q(1+d)，两因子均≥2，所以合数，出语言。证明只用总长度，不要求v或y各自非空，只需合计非空。自取q=5,d=2时i=6，长度15=5×3，展示相同计算。

回到正文：平方计数与素数长度

来源与证据

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

• 原件：L08-上下文无关语言性质-资料包.pdf（本地课件），PDF p.1–136。

• 本次独立学习修订：核对本讲178页文本，视觉复核 p.25、32、93、131–136、152、160、162、177；将树高证明放入正文，并修正乘积图漏写栈底检查的问题。