CSCI3130 HW03 · 2026T1 逐题详细解析

原题：HW3_2026.pdf（本地课件），p.1；题面日期为 2026-10-12 至 2026-10-19。用途：从必要概念开始，解释怎样想到解法、逐步完成证明或构造，再检验边界；这是学习解析。覆盖：Q1(1)、Q1(2)、Q2、Q3、Q4，全部五个小问。配套：L04–L05 完整知识串讲，补足作业未直接考到的封闭性、判定算法、解析与程序语言内容。约定：空串记作 $\varepsilon$ ，对应讲义的 $\lambda$ ；泵长用 $p$ ，泵段长度用 $t$ ，避免与题目的计数变量混淆。

题面分值依次是 30、15、25、20，合计 90 分；此处忠实保留原标注，不擅自改成 100 分。五个小问的题面、规则、推导树和证明均在正文内。

先知道每一题要学会什么

这份作业跨过一个重要分界：Q1 问“有限状态机做不到什么”，Q2–Q3 问“递归文法怎样生成这种结构”，Q4 问“同一个字符串能不能有两种结构解释”。nonregular 不等于没有文法，更不等于不是 context-free。

小问	已知与要求	依赖知识	本文输出
Q1(1)	三段计数满足不等式；证明非正则	L04 泵引理、边界选串、所有切分	泵掉前段后破坏不等式的完整反证
Q1(2)	长度为 3 的非负整数次幂；证明非正则	泵引理、相邻合法长度之间的空隙	把泵后长度夹在相邻幂之间
Q2	等量 a/b 加任意正数量 c；找 CFG	CFG、配对递归、独立拼接	文法、推导、两个包含方向
Q3	ab/ba 块数与 d 数量匹配；找 s-grammar	CFG、终结符提取、唯一预测	普通 CFG 到 s-grammar，完整解析轨迹
Q4	给定文法；证明歧义	推导树、最左推导、存在性证据	同串的两条最左推导与两棵树

五问之间没有必须借用前问答案的依赖。第一次学习建议按本文顺序读；只忘了某个概念，可直接跳到相应小问，必要定义均在本问内给出。

Q1 公共工具：泵引理究竟保证什么

题面（HW3_2026.pdf · Q1 公共要求 · p.1）

p.1 Q1. (30pts) Proof that the following languages are not regular:

从 DFA 推出泵引理

正则语言是能被某个确定有限自动机 DFA 恰好识别的语言。DFA 的记忆完全体现在当前状态中；若两个不同的输入前缀把它带到同一个状态，此后接上相同后缀，它的接受或拒绝结果就一定相同。

假设 DFA 有 $p$ 个状态。读取前 $p$ 个字符时，连同读入之前的初态，记录了 $p+1$ 个状态位置。位置比可用状态多，因此有两次记录相同。这是鸽巢原理。

设重复发生在读完第 $r$ 与第 $s$ 个字符时， $0\le r<s\le p$ 。把字符串切成：前 $r$ 个字符是 $x$ ，随后 $s-r$ 个是 $y$ ，其余是 $z$ 。读 $y$ 会从某状态绕一圈回到自身。因此可以不绕、绕一次、绕两次，再接着读 $z$ ，最终状态都不变。

由此得到：若 $L$ 正则，则存在 $p\ge1$ ，使每个 $w\in L$ 、 $\lvert w\rvert\ge p$ 都存在切分 $w=xyz$ ，满足

\lvert xy\rvert\le p,\qquad \lvert y\rvert\ge1, \qquad xy^iz\in L\quad\text{for every integer }i\ge0.

前两个条件分别来自 $s\le p$ 和 $s-r\ge1$ 。 $x$ 或 $z$ 可以为空， $y$ 不可以为空。 $i=0$ 产生 $xz$ ， $i=1$ 是原串， $i=2$ 是 $xyyz$ ；指数只作用于 $y$ 。

把定理反过来用于反证

定理只保证“至少一种切分对所有 i 都有效”。为了推翻它，需要让“每一种合乎长度限制的切分，至少有一个 i 失败”。可记成选择顺序：

\text{regular:}\quad \exists p\;\forall w\;\exists(x,y,z)\;\forall i.

这里的 $w$ 和切分分别受上面的成员、长度条件限制。要证明违反该性质，顺序变成：

\forall p\;\exists w\;\forall(x,y,z)\;\exists i \quad\text{such that }xy^iz\notin L.

所以你不能固定 $p=10$ ，不能只试一种切分，也不能把不属于 $L$ 的串拿来泵。你可以在知道 $p$ 后选 $w$ ，在知道切分后选 $i$ ； $i$ 可以依赖 $y$ 的长度。本作业两题恰好都能用一个固定的 $i$ 打败全部切分。

来源：L04 p.62–75、p.96–99。这里补出了讲义状态计数和量词否定的中间步骤。

Q1(1)：三段计数的不等式语言

题面（HW3_2026.pdf · Q1(1) · p.1）

p.1 1) $L=\{a^nb^la^k:k\le n+l\}$

公式按原题重排。题面未再次写出 $n,l,k$ 的取值范围，按字符串幂的通常约定取非负整数；下面所选三个指数都为正，因此即使课程约定从正整数开始，证明仍成立。

先读懂语言，不急着写证明

字符串由三段组成：开头 $n$ 个 a，中间 $l$ 个 b，结尾 $k$ 个 a；最后那段 a 的数量不能超过前两段总长度。

演示（自取数字，非原题数据）： $n=2,l=3,k=5$ 时，串为 aabbbaaaaa，因为 $5\le2+3$ ，属于语言。若最后改成 6 个 a，就不属于语言。

我们想改变哪一段？由于 $\lvert xy\rvert\le p$ ，只要开头放至少 $p$ 个 a，就能把所有可能的泵段 $y$ 锁在第一段 a 中。接着让不等式恰好取等号；一旦从第一段删掉 a，右边 $n+l$ 就减小，而左边 $k$ 保持不变，必然越界。

这给出选串：

w=a^pb^pa^{2p}.

中间保留非空的 b 段也很重要：它把两段 a 分隔开，泵后不能通过重新划分一整段连续 a 来“救回”成员资格。

完整证明，每步说明理由

假设 $L$ 正则，令 $p\ge1$ 为泵长。取 $w=a^pb^pa^{2p}$ 。

它属于 $L$ ：取 $n=p,l=p,k=2p$ ，有 $k=n+l$ 。此外 $\lvert w\rvert=4p\ge p$ ，因此引理适用。

考虑任意满足 $w=xyz$ 、 $\lvert xy\rvert\le p$ 、 $\lvert y\rvert\ge1$ 的切分。前 $p$ 个字符全为 a，因此必有

y=a^t,\qquad1\le t\le p.

这里没有假设 $x$ 是空串，也没有选定 $y$ 的具体长度。无论对方把它切在哪里，删掉它都只会让第一段 a 少 $t$ 个。

取 $i=0$ ，于是

xy^0z=xz=a^{p-t}b^pa^{2p}.

泵后由 b 段唯一确定三段的计数：

n'=p-t,\qquad l'=p,\qquad k'=2p.

代入语言条件：

n'+l'=(p-t)+p=2p-t<2p=k'.

因此 $xz\notin L$ 。但引理要求选出的好切分在 $i=0$ 时仍属于 $L$ 。我们证明每个合法切分都会失败，矛盾。因此 $L$ 非正则。

验算边界与常见错误

当 $t=p$ 时第一段完全消失，变成 $b^pa^{2p}$ ；此时 $n'=0,l'=p,k'=2p$ ，仍然违反 $2p\le p$ 。若指数必须为正，它更直接因没有前段 a 而被排除。

演示（自取数字）： $p=3$ ，原计数为 $(3,3,6)$ 。 $t=1,2,3$ 时，泵后前两段长度分别为 5、4、3，而最后一段始终是 6，所以全部失败。

为什么不取 $i=2$ ？因为泵大第一段会使 $n+l$ 增大，原本 $k\le n+l$ 仍然成立。本题要攻击的是这个不等式的上界，泵的方向必须选对。

为什么不选最后一段很短的串？例如 $a^pb^pa$ ，删掉前面一点 a 往往仍满足条件。选串“贴着边界”才能让任何非零变化都越界。

整理后的简洁证明

Suppose that $L$ is regular and let $p$ be a pumping length. Choose $w=a^pb^pa^{2p}\in L$ , with $\lvert w\rvert=4p\ge p$ . For any decomposition $w=xyz$ satisfying $\lvert xy\rvert\le p$ and $\lvert y\rvert\ge1$ , we have $y=a^t$ for some $1\le t\le p$ . Pumping down gives $xz=a^{p-t}b^pa^{2p}$ . Since $2p>(p-t)+p$ , and the nonempty block of b's fixes the two surrounding a-blocks, $xz\notin L$ . This contradicts the pumping lemma. Hence $L$ is not regular.

Q1(2)：长度只能是 3 的幂

题面（HW3_2026.pdf · Q1(2) · p.1）

p.1 2) $L=\{a^{3^n}:n\ge0\}$

公式按原题重排，并已核对 PDF 图像：指数是 $3^n$ ，不是 $3n$ 。若是 $3n$ ，语言就可以用正则表达式 $(aaa)^\ast$ 表示，答案完全不同。

先把“双层指数”读清楚

外层 $a^N$ 表示 N 个 a；这里 $N=3^n$ 。因此合法长度为

1,3,9,27,81,\ldots

$n=0$ 给出 $a$ ，不是空串。字符串不是 a3，也不是把字符 3 放进去。

此题没有 a/b 两种字母的数量关系可破坏；能攻击的是合法长度之间越来越大的空隙。泵一次至多增加 $p$ 个字符，如果这点增加不足以到下一个合法长度，就会掉进空隙。

为什么不能直接选 a 的 p 次方

泵长 $p$ 是任意正整数，未必是 3 的幂，所以 $a^p$ 不一定属于语言。必须先保证见证串合法。

选择 $w=a^{3^p}$ 则同时满足：指数 $p$ 是整数，所以 $w\in L$ ；且 $3^p\ge p$ ，因此长度足够。这里选择的不是“泵长等于 $3^p$ ”，泵长依然是 $p$ 。

完整证明

假设 $L$ 正则，令 $p\ge1$ 为泵长，选 $w=a^{3^p}$ 。对任意合法切分 $w=xyz$ ，由于整个串只有 a，可写

y=a^t,\qquad1\le t\le p.

取 $i=2$ ，多放一份 $y$ 。原串已经有一份 $y$ ，所以只额外增加 $t$ ，不是增加 $2t$ ：

xy^2z=a^{3^p+t}.

检查长度。因为 $t\ge1$ ，有 $3^p+t>3^p$ 。另一方面， $t\le p\le3^p$ ，所以

3^p+t\le3^p+p\le2\cdot3^p<3\cdot3^p=3^{p+1}.

于是

3^p<3^p+t<3^{p+1}.

两个相邻的整数次幂 $3^p$ 与 $3^{p+1}$ 之间没有其他 3 的整数次幂。因此泵后的长度不是合法长度， $xy^2z\notin L$ ，与泵引理矛盾，故 $L$ 非正则。

演示（自取数字）：若 $p=3$ ，原长度 $3^3=27$ ，下一合法长度是 81。 $t$ 只能为 1、2、3，泵后长度为 28、29、30，全部落在 27 与 81 之间。正式证明中的不等式，就是把这个检查推广到全部 $p$ 和全部 $t$ 。

可以迁移的思路

对于单字母语言，不能只说“增长很快，所以不正则”；真正需要的是：选到一个合法长度，证明泵导致的有限增量小于下一合法长度的间隔。L04 p.93 的平方数例子采用同一类间隔论证，本题把平方数换成了 3 的幂。

通用计数式是

\lvert xy^iz\rvert=\lvert w\rvert+(i-1)\lvert y\rvert.

检查 $i=0,1,2$ ，分别是减一段、不变、加一段，就不会把 $i$ 与“额外复制次数”混淆。

整理后的简洁证明

Suppose that $L$ is regular and let $p\ge1$ be a pumping length. Choose $w=a^{3^p}\in L$ . For every valid decomposition $w=xyz$ , let $y=a^t$ , where $1\le t\le p$ . Then $xy^2z=a^{3^p+t}$ . Since $3^p<3^p+t\le3^p+p\le2\cdot3^p<3^{p+1}$ , its length lies strictly between two consecutive powers of 3. Hence $xy^2z\notin L$ , contradicting the pumping lemma. Therefore $L$ is not regular.

Q2：等量 a/b 与独立的 c 段

题面（HW3_2026.pdf · Q2 · p.1）

p.1 Q2. (15pts) Find context-free grammar for the following language:

$L=\{w\in\{a,b,c\}^{\ast}:w=a^kb^kc^l,\ k,l\ge1\}$

公式按原题重排。

CFG 是什么，为什么它适合表达配对

上下文无关文法 CFG 写成 $G=(V,T,S,P)$ 。 $V$ 是变量或非终结符的集合， $T$ 是终结符的集合， $S$ 是开始变量， $P$ 是产生式集合。终结符是最终答案里真正留下的字符；变量是尚待展开的结构。

CFG 的规则左侧必须是单个变量，例如 $A\to aAb$ 。右侧可含终结符、变量，也可为空。展开 A 时，不必检查它旁边是什么字符，这就是“上下文无关”。来源：L05 p.7–9。

$A\to aAb$ 的意义不是“同时选择两个独立数量”，而是每用一次规则，左侧增加一个 a、右侧增加一个 b，天然让两者同步增长。递归调用 A 留在中间，确保全部 a 出现在全部 b 前面。来源：L05 p.10–12。

本题还有一个独立的 c 段。 $k$ 决定 a/b 的数量， $l$ 决定 c 的数量，两个参数不必相等。因此将任务拆成两个变量：A 生成等量 a/b，C 生成任意正数量 c，再把它们拼起来。

从边界条件设计规则

因为 $k\ge1$ ，最小的 a/b 部分是 ab，不是空串。所以令

A\to aAb\mid ab.

因为 $l\ge1$ ，最小 c 部分是 c，所以令

C\to cC\mid c.

最后拼接：

S\to AC.

完整答案为

\begin{aligned} V&=\{S,A,C\},\qquad T=\{a,b,c\},\\ P:\qquad S&\to AC,\\ A&\to aAb\mid ab,\\ C&\to cC\mid c. \end{aligned}

竖线表示可选择其中一条规则，不是最终字符串的一部分。

真的推导一次

演示（自取参数）：取 $k=2,l=3$ ，目标是 aabbccc。

\begin{aligned} S&\Rightarrow AC\\ &\Rightarrow aAbC\\ &\Rightarrow aabbC\\ &\Rightarrow aabbcC\\ &\Rightarrow aabbccC\\ &\Rightarrow aabbccc. \end{aligned}

第二行对 A 用一次递归；第三行对 A 用 ab 收尾。后面 C 递归两次，用 c 收尾。a/b 同步，c 的次数独立。

为什么它生成的恰好就是题目语言

只列规则和一个例子还不足以证明“恰好”。要检查两个方向。

方向一：不会多生成。 A 递归 $r\ge0$ 次，再用 $A\to ab$ 收尾，结果一定是 $a^{r+1}b^{r+1}$ 。C 递归 $s\ge0$ 次，再用 $C\to c$ 收尾，结果一定是 $c^{s+1}$ 。S 只能先变成 AC，因此每个最终串都形如 $a^{r+1}b^{r+1}c^{s+1}$ ，满足 $k,l\ge1$ 。

方向二：不会少生成。 对任意题目允许的 $k,l\ge1$ ，令 A 递归 $k-1$ 次、C 递归 $l-1$ 次，然后分别收尾，即可得到所要求的 $a^kb^kc^l$ 。因为 $k-1,l-1\ge0$ ，这些次数都合法。

两方向合起来才是 $L(G)=L$ 。

易错点

把 A 的收尾写成空串，会允许 $k=0$ ，额外生成 c、cc 等。
把 C 的收尾写成空串，会允许 $l=0$ ，额外生成 ab、aabb 等。
用三个互相独立的变量生成 a、b、c，会丢失 a 与 b 数量相等的约束。
试图用 $S\to aSbc$ 让三个计数一起变化，会改变字符串顺序，还错误地把 c 的数量绑定到 k。

最小合法串 abc 的推导是 $S\Rightarrow AC\Rightarrow abC\Rightarrow abc$ 。这是检查“至少一个”的最简单边界测试。

Q3：先构造 CFG，再做成 s-grammar

题面（HW3_2026.pdf · Q3 · p.1）

p.1 Q3. (25pts) Find simple grammar (s-grammar) for the following language:

$L=\{wcd^n:w\in\{ab,ba\}^{n},\ n\ge0\}$

(For example, the string $abbacdd$ is in $L$ .)

(Hint: You can first construct a CFG, then make the CFG simple.)

公式按原题重排。这里 w 是一个字符串，不是一个新终结符。

先理解集合的 n 次幂

$w\in\{ab,ba\}^{n}$ 的意思是：选取 n 个块，每个块独立选 ab 或 ba，然后依次拼接。

n	可以选的 w	最终字符串
0	空串	`c`
1	`ab`、`ba`	`abcd`、`bacd`
2	`abab`、`abba`、`baab`、`baba`	`abab c dd`、`abba c dd`、`baab c dd`、`baba c dd`

表格最后一行的空格只是标段，实际串没有空格。特别是 abba 允许混合选择，不是只允许 $(ab)^n$ 或 $(ba)^n$ 。

每增加一个长度为 2 的块，就要在 c 后多一个 d。最终长度是 $2n+1+n=3n+1$ ，但“长度为 $3n+1$ ”只是必要条件，还必须满足块结构、唯一的 c 和 d 的位置。

第一步：设计普通 CFG

若暂时不管 simple 的限制，很自然写成

S\to abSd\mid baSd\mid c.

两条递归规则分别在前面加一个块，在末尾加一个 d；中间 S 继续完成剩余块。 $S\to c$ 对应零个块、零个 d。

用原题的 abbacdd 走一遍：

S\Rightarrow abSd\Rightarrow abbaSdd\Rightarrow abbacdd.

第一次选 ab，第二次选 ba，最后用 c 收尾。每一层留下的 d 最终排在 c 的右侧。

第二步：s-grammar 比 CFG 多要求什么

L05 p.54 的定义有两个条件，缺一个都不算：

每条规则形如 $A\to a\alpha$ ：最前面恰好一个终结符，后面 $\alpha\in V^\ast$ 只能是变量串，可以为空。
对同一个左侧变量 A 和同一个开头终结符 a，至多有一条规则。

第一条使每次展开正好输出一个字符；第二条使“当前要展开的变量 + 下一个输入字符”唯一决定规则。

普通规则 $S\to abSd$ 不符合第一条：开头 a 后面还有终结符 b 和 d。因此“规则已经以终结符开头”还不够，后面的字符类型也要检查。

第三步：用变量承接剩余字符

把第一条规则在首字符 a 后的剩余任务 bSd 交给 A；把第二条规则在首字符 b 后的剩余任务 aSd 交给 B；再用 D 负责一个 d。

得到最终文法：

\begin{aligned} S&\to aA\mid bB\mid c,\\ A&\to bSD,\\ B&\to aSD,\\ D&\to d. \end{aligned}

其中 $V=\{S,A,B,D\}$ ， $T=\{a,b,c,d\}$ ，开始变量为 S。A、B 的名字没有固定含义；此处 A 是“已经读了一个块的首字母 a，接下来必须补 b”，B 则反过来。

逐条检查 simple 条件

规则	首终结符	后面是否仅有变量	决策对
$S\to aA$	a	A，是	$(S,a)$
$S\to bB$	b	B，是	$(S,b)$
$S\to c$	c	空串，是	$(S,c)$
$A\to bSD$	b	SD，是	$(A,b)$
$B\to aSD$	a	SD，是	$(B,a)$
$D\to d$	d	空串，是	$(D,d)$

六个决策对没有重复，因此符合第二条。不同左变量的规则可以同以 a 开头，例如 $S\to aA$ 与 $B\to aSD$ 没有冲突，因为当前变量不同。

$S\to c$ 是允许的：它输出一个终结符，后面接零个变量。它不是空产生式。s-grammar 在本讲定义下没有 $S\to\varepsilon$ ；本题包含的是 c，不是空串，因此没有冲突。

用最终文法推导原题样例

\begin{aligned} S&\Rightarrow aA\\ &\Rightarrow abSD\\ &\Rightarrow abbBD\\ &\Rightarrow abbaSDD\\ &\Rightarrow abbacDD\\ &\Rightarrow abbacdD\\ &\Rightarrow abbacdd. \end{aligned}

每步展开的都是最左边变量。注意 $S\Rightarrow bB$ 时旧的 D 还留在右边；随后 $B\Rightarrow aSD$ 又新增一个 D，所以会得到两个 D，而不是覆盖原来的 D。

为什么语言没有被转换改变

普通 CFG 的一次 $S\to abSd$ ，在新文法中对应 $S\Rightarrow aA\Rightarrow abSD$ ，最后 D 必须变成 d。另一条递归也一样对应 $S\Rightarrow bB\Rightarrow baSD$ 。停止规则仍然输出 c。

因此每次递归恰好生成一个 ab/ba 块和一个 D。递归 n 次后，剩下中间 S 与右侧 n 个 D；把 S 变成 c、所有 D 变成 d，就得到 $wcd^n$ ，其中 w 是 n 个允许块的拼接。这证明不会生成非法串。

反过来，对任何给定的合法串，把 c 前面的 w 按每两个字符分成 n 个块。每遇到 ab 就选择第一条递归，每遇到 ba 就选择第二条；n 次后输出 c，再输出 n 个 d。故每个合法串都能生成。

这个文法为什么可以边读边决定

解析 abbacdd 时，维护待完成变量串，最左边视为接下来要处理的变量：

已读前缀	下一个输入	待完成变量	必须采用的规则	新待完成变量
空	a	S	$S\to aA$	A
a	b	A	$A\to bSD$	SD
ab	b	SD	$S\to bB$	BD
abb	a	BD	$B\to aSD$	SDD
abba	c	SDD	$S\to c$	DD
abbac	d	DD	$D\to d$	D
abbacd	d	D	$D\to d$	空

输入与待完成变量同时用完，接受。若输入是 abbacd，读完后还剩一个 D，拒绝；若是 abbacddd，待完成变量用完后还有输入，也拒绝。这说明“能一路匹配前缀”不等于完整接受。

在固定文法下，每步消耗一个输入字符、选一条规则，不回溯，因而是线性时间。这并不意味着语言正则：待完成的 D 可以任意多，承担了无界计数的作用，有限状态机没有这份无界存储。来源：L05 p.54–56；待完成变量表为本题的解析演示。

Q4：给同一个字符串两种结构

题面（HW3_2026.pdf · Q4 · p.1）

p.1 Q4. (20pts) Show that the following grammar is ambiguous:

$S\to SS\mid aEcS\mid d$

$E\to b$

(Recall: A CFG G is ambiguous if some string $w\in L(G)$ has two or more [derivation trees/leftmost derivations/rightmost derivations].)

公式按原题重排。

歧义在比较什么

一个文法有歧义，意思是存在至少一个合法字符串，有两棵不同的完整推导树。等价地，可以给同一个串写出两条不同的最左推导，或两条不同的最右推导。来源：L05 p.64–65。

最左推导不是“每次随便选择一条左侧规则”，而是每一步都展开当前句型最左边的非终结符。规则本身可以选，但展开位置固定。

为什么普通的两条推导不够？例如 $S\to AB,A\to a,B\to b$ ：先展开 A 或先展开 B 都能得到 ab，但只对应一棵树。不同的执行先后顺序不必产生不同的结构。L05 p.38 正在说明这个区别。

怎样找到最省力的歧义见证

观察 $S\to SS$ ：一个 S 可以表示两个 S 的拼接；而 $S\to d$ 让每个 S 又能成为一个 d。

对两个 d，只有一次二元拼接。对三个 d，就可以先拼前两个，也可以先拼后两个：

(dd)d\qquad\text{or}\qquad d(dd).

括号表示树的分组，不是字符串中的字符。因此选择见证串 $w=ddd$ 。

不必使用 $S\to aEcS$ 或 $E\to b$ 。歧义是存在性结论；只要文法允许的部分规则已经给出一个证据，就足够证明整个文法有歧义。

第一条最左推导：先把左侧 S 拆成两个

\begin{aligned} S&\Rightarrow SS\\ &\Rightarrow SSS\\ &\Rightarrow dSS\\ &\Rightarrow ddS\\ &\Rightarrow ddd. \end{aligned}

第二步展开的是两个 S 中左边那个。三个 S 出现后，依次把最左边的 S 变成 d。根的左子树产出 dd，右子树产出 d，对应 $(dd)d$ 。

第二条最左推导：先把左侧 S 收尾为 d

\begin{aligned} S&\Rightarrow SS\\ &\Rightarrow dS\\ &\Rightarrow dSS\\ &\Rightarrow ddS\\ &\Rightarrow ddd. \end{aligned}

第二步把最左边的 S 直接变成 d；第三步才展开剩余的 S。此时该 S 虽然位于 d 的右边，但它仍然是当前最左边的非终结符，所以没有违反最左推导要求。根的左子树产出 d，右子树产出 dd，对应 $d(dd)$ 。

两棵推导树（本题自绘示意）

树一：(dd)d                    树二：d(dd)

         S                            S
       /   \                        /   \
      S     S                      S     S
     / \    |                      |    / \
    S   S   d                      d   S   S
    |   |                              |   |
    d   d                              d   d

两棵树从左到右的叶子都是 d、d、d，但内部的父子关系不同。两条最左推导的第二步也已经不同，所以不是重复书写同一个证据。

因此存在 $ddd\in L(G)$ ，具有两棵不同推导树（等价地，两条不同最左推导），故 G 有歧义。

还要分清文法与语言

本题只证明“这套规则有歧义”，没有证明“这个语言任何文法都必然有歧义”。后者叫固有歧义，要求排除所有等价文法，远强于本题。两个概念的区别见配套串讲的 L05 部分。

五问放在一起，你应掌握的解题动作

看到的结构	第一反应	必须补上的正确性检查
计数不等式	让见证串位于边界，决定该泵大还是泵小	任意 y、泵后重新代入不等式、块边界是否唯一
稀疏单字母长度	将泵后长度夹在相邻合法长度之间	原长是否合法、严格不等式、是否包括最小泵长
两段数量相等	在同一递归规则两侧各加一个字符	字符顺序、零次递归的终止条件
额外独立一段	用独立变量生成后拼接	不要让独立参数被绑定，不要漏掉正数约束
一块对应一个尾字符	每次递归前面加块、后面加尾字符	n=0、混合块、块数与字符数不能混淆
要求 s-grammar	一个首终结符后仅接变量，同一决策对唯一	不是任意 CFG 都自动符合，也不能漏查单终结符规则
证明歧义	找同串的两种分组	两棵树或两条同类规范推导，不能只换展开顺序

按小问完成检查

Q1(1)：已验证见证串成员资格、长度、任意切分、删空首段边界以及泵后违反条件；给出完整反证。
Q1(2)：已视觉核对双层指数，推导严格的相邻幂界限，给出完整反证。
Q2：已列 CFG 的符号和全部规则，展开实例，证明生成语言的两个包含方向，检查两个正数约束。
Q3：已按提示从普通 CFG 转成 s-grammar，逐条核条件，完成原题样例推导、双向语言证明与解析轨迹。
Q4：已给出同一个串 ddd 的两条不同最左推导与两棵树，说明未使用其他规则不影响存在性证明。
本文未省略原题小问；补充的 lec4–5 知识见配套文档。小规模程序枚举用于查错，不替代以上一般证明，具体范围记录于核验文件。

来源与证据

原题：HW3_2026.pdf（本地课件），p.1，文本与整页图像均已核对。原件保留在用户指定位置，未复制第二份。
课件：L04-正则语言性质-资料包.pdf（本地课件），重点 p.62–75、p.77–100；L05-上下文无关文法-资料包.pdf（本地课件），重点 p.7–15、p.22–38、p.54–65。
方法依据课件；本作业的文法、证明、推导树和解析轨迹为针对当前题目的独立推导。自取参数已就地注明。
考试证据：读了 HW3_2026.pdf；未识别用途的 PDF：无。
未读：HW03-手写作答-202510211114.pdf、HW03-2025T1-参考解答.pdf、HW03-2025T1-题目.pdf（往年材料，不作为本次题目或答案依据）。

2026-10-13 独立学习复核：按 p.1 全部五个小问核对题面与解答；配套 L04–L05 串讲同步补入本轮原图表及演算内容。