CSCI3130 L04–L05：从正则语言的边界到上下文无关文法

范围：L04 正则语言性质、L05 上下文无关文法的全部主要知识点；以当前 HW3 的学习需要串联，补足未被作业覆盖的内容。配套：HW03 逐题详细解析，五小问的必要解法均在该文件内完整给出。原件：L04（本地课件）共 103 页；L05（本地课件）共 90 页。下文页码均为 PDF 页号。读法：首次学习按本文顺序读；每到作业对应点，可去做该小问。本文是按知识组织的完整串讲，不逐张重复课件动画和过渡页。记号：空串统一写 epsilon 对应的数学符号，讲义 lambda 表示同一对象；推导和集合运算的符号在使用前解释。

阅读路线与两讲的关系

这两讲讨论的对象始终是语言，即“哪些有限字符串算合法”的集合。L04 研究有限状态机可以识别的语言有什么共同性质，以及怎样证明某语言超出了它的能力。L05 引入递归生成规则，让我们能描述等量配对、嵌套和程序语法，再研究同一个字符串的结构能否唯一确定。

建议按四段推进，每段读完能完成一个可检验动作：

基础与封闭性：能说明为什么并、交、补、拼接等操作保留正则性，并实际构造乘积状态。
判定与非正则证明：能区分空语言、有限语言和非正则语言；能独立完成 HW3 Q1。
CFG 与生成结构：能从目标串的结构设计规则，并检查生成语言恰好正确；完成 Q2。
解析、s-grammar 与歧义：能根据输入选择规则，分清展开顺序与结构差异；完成 Q3–Q4，再理解编译器中的用途。

不需要先学后续讲次的下推自动机转换、乔姆斯基范式或 CYK 动态规划表才能完成本作业。L05 只预告了其中部分概念，本文也清楚区分预告与本讲推导。

0. 最少但不能省的符号基础

字母表 $\Sigma$ 是有限符号集合，例如 $\{a,b\}$ ；字符串是有限个符号依次排列，例如 aabb；语言是字符串的集合，例如 $\{a^nb^n:n\ge0\}$ 。

记号	含义	一次检查
$\varepsilon$	长度为 0 的字符串	它是一个字符串
$\varnothing$	没有任何字符串的语言	它与 $\{\varepsilon\}$ 不同
$\Sigma^\ast$	该字母表上的所有有限串，包括空串	a、ab、空串都可在其中
$a^n$	n 个字符 a 的拼接	$a^0=\varepsilon$
$uv$	先放 u，再放 v	ab 拼 ba 得 abba
$w^R$	字符顺序反转	$(aab)^R=baa$
$\lvert w\rvert$	字符串长度	$\lvert abba\rvert=4$
$n_a(w)$	w 中 a 的总个数	不要求 a 连续出现

正则语言 regular language 可由 DFA、NFA、正则表达式或正则文法表示，四种表示法表达能力相同。不同表示法不一定同样便于某种证明：补集适合 DFA，拼接适合带空边的 NFA，同态适合替换正则表达式。

补充直觉：有限状态不是完全不能“计数”。例如奇偶性只需要记“偶/奇”，模 3 只需要 3 种余数。真正困难的是没有固定上限的精确对应，如任意多个 a 后还必须记住恰好同样多个 b。

1. L04：封闭性为什么能成为证明工具

来源：L04 p.3–32；对应已有课程条目 #L04-01、#L04-02、#L04-03。

“正则语言对某操作封闭”是一个带前提的承诺：如果输入语言都是正则的，那么做完操作得到的语言也正则。它不是说任意语言做此操作都会变正则，也不是说正则语言的每一个子集都正则。

1.1 并、拼接、星：通过空边组合 NFA

并集 $L_1\cup L_2$ 表示“属于至少一个”。拼接 $L_1L_2$ 表示先取 $u\in L_1$ ，再取 $v\in L_2$ ，输出 uv。星 $L^\ast$ 表示有限次拼接，可取零次，因此一定包含空串。

证明时，可先把每台 NFA 整理成独立的状态集合和单一入口、单一出口。多个原终态可用不消耗输入的 $\varepsilon$ 边接到新出口。空边不是读取一个名叫 epsilon 的字符，而是无需读字符就能换状态。

并：新增初态，通过两条空边分别进入两台机器；任一分支能接受就接受。这正对应“或者”。
拼接：把第一台的出口用空边接到第二台入口；只把第二台出口作为新终态。一次接受路径把输入分成先由第一台接受、再由第二台接受的两段。
星：新增入口和出口，允许入口直接空跳到出口，表示零次；允许进入原机器，每完成一次既可结束，也可空跳回原入口再来一次。

这些构造仍然只有有限个状态，所以仍是 NFA；NFA 与 DFA 等价，因此输出语言正则。

讲义算例（L04 p.6、p.8、p.10、p.12）：取 $L_1=\{a^nb:n\ge0\}$ ， $L_2=\{ba\}$ 。这是原页给出的两个语言，公式按讲义重排。

并集包含 b、ab、aab 及 ba。拼接必须实际接在一起：

L_1L_2=\{a^nbba:n\ge0\}.

星中的每一块为“若干 a 后接一个 b”，所以允许零块的空串，也允许多个这样的块。不能把 $L_1^\ast$ 错写为“只重复单个 a”。

1.2 反转：把接受路径倒过来

将上述单入口、单出口 NFA 的全部箭头反向，再交换入口与出口。原本从初态读 w 到终态的路径，反向后从新初态读 $w^R$ 到新终态，所以恰好识别 $L^R$ 。反向后一般是 NFA，不要求它保持确定性。

若未预先合并多个终态，应新建初态并用空边连接所有旧终态；不能随便挑一个旧终态，否则漏掉原语言的部分字符串。来源：L04 p.13–14。

1.3 补集：为什么必须用完整 DFA

补集始终相对于一个固定字母表：

\overline L=\Sigma^\ast\setminus L.

完整 DFA 对每个状态、每个输入符号都有唯一转移，每个字符串都有唯一的完整运行。把接受状态和非接受状态互换，就把所有字符串的判断结果反转。

若某些边缺失，先补一个陷阱状态：缺边进入它，它对每个符号都转回自己。否则原来“走不下去”的串在交换终态后仍走不下去，无法变成应有的接受。

也不能直接对 NFA 交换终态。NFA 接受表示“存在一条接受路径”，拒绝表示“所有路径都拒绝”。把每条路径的终态标记换掉，得到的是“存在一条原本拒绝的路径”，它不等价于“没有原本接受的路径”。来源：L04 p.15–16；NFA 的量词解释为补充。

1.4 交、差与乘积自动机：同时记两台机器的位置

如果两台 DFA 分别处于状态 u 与 v，新机器记录状态对 $(u,v)$ 。读同一个字符 t 时，让两台机器各走一步：

\delta((u,v),t)=(\delta_1(u,t),\delta_2(v,t)).

若两台各有 r、s 个状态，最多需要 $rs$ 个状态，仍然有限。初态是两个初态组成的状态对。关键是换不同的接受条件：

目标操作	状态对接受的条件
交 $L_1\cap L_2$	两边都接受
并 $L_1\cup L_2$	至少一边接受
差 $L_1\setminus L_2$	第一边接受且第二边拒绝
对称差	恰好一边接受

题面/算例来源（L04 p.17）

p.17 $L_1=\{x\mid 00\text{ is not a substring of }x\}$

$L_2=\{x\mid x\text{ ends in }01\}$

公式按讲义重排。p.18 两台 DFA 已视觉核对：第一台初态 A、终态 A/B，C 是陷阱；第二台初态 X、唯一终态 Z。全部转移如下：

第一台状态	读 0	读 1	接受？
A	B	A	是
B	C	A	是
C	C	C	否

第二台状态	读 0	读 1	接受？
X	Y	X	否
Y	Y	Z	否
Z	Y	X	是

A 表示还没出现 00 且当前不以 0 结尾，B 表示还没出现 00 且末位为 0，C 表示已经失败。X/Y/Z 分别对应当前后缀对“01”的匹配进度：无有效匹配、已匹配 0、已匹配 01。

现在从 AX 出发，所有可达状态的表为：

乘积状态	读 0	读 1	交接受	差接受
AX	BY	AX	否	是
BY	CY	AZ	否	是
AZ	BY	AX	是	否
CY	CY	CZ	否	否
CZ	CY	CX	否	否
CX	CY	CX	否	否

例如 $\delta(AX,0)=(B,Y)$ ，因为两台读 0 后分别到 B、Y。全集有 9 个状态对，AY、BX、BZ 从 AX 不可达，可省略。交的全部理论终态为 AZ、BZ，其中只有 AZ 可达。

补充执行演示：101 的轨迹为 AX→AX→BY→AZ，没有 00 且以 01 结尾，交接受；001 的轨迹为 AX→BY→CY→CZ，虽然以 01 结尾，但已经有 00，交拒绝。10 最后在 BY，属于第一语言而不属于第二语言，所以差接受。

1.5 用集合恒等式也能证明封闭性

德摩根律给出

L_1\cap L_2=\overline{\overline{L_1}\cup\overline{L_2}}, \qquad L_1\setminus L_2=L_1\cap\overline{L_2}.

已知补与并保留正则性，就能推出交；再由交与补推出差。证明时每一步都要说明使用的语言确实正则。来源：L04 p.26–28。

1.6 同态：把每个字母替换成固定字符串

同态 $h:\Sigma\to\Gamma^\ast$ 为每个输入字母指定一个输出串，延伸到字符串时按原顺序拼接： $h(uv)=h(u)h(v)$ ，并令 $h(\varepsilon)=\varepsilon$ 。

讲义算例（L04 p.30）

p.30 $h(a)=ab,\ h(b)=bbc.$

The homomorphic image of $L=\{aa,aba\}$ is $h(L)=\{abab,abbbcab\}$ .

公式按讲义重排。逐字替换可检查为 $h(aba)=h(a)h(b)h(a)=ab\,bbc\,ab=abbbcab$ 。同一个字母每次必须用同一替换，不能按所在位置改变规则。

如果正则表达式 r 描述 L，将 r 中每个字母替换为其 h 像，保留并、拼接与星的结构，就得到描述 $h(L)$ 的正则表达式。因此正则语言的同态像仍然正则。

讲义算例（L04 p.31）： $h(a)=dbcc,h(b)=bdc,r=(a+b^\ast)(aa)^\ast$ 。替换后为

(dbcc+(bdc)^\ast)(dbccdbcc)^\ast.

这里 + 表示正则表达式的并，星作用于整个被括起来的块。

1.7 封闭性如何用于非正则证明

逻辑是：假设目标语言 L 正则，经过已知保正则的操作得到 K；若 K 已被证明非正则，就矛盾。

常用“过滤”是与一个正则语言 R 取交，只留下容易分析的字符串。关键等式必须证明为 $L\cap R=K$ ，不能只证明 K 是它的子集。因为正则语言也可以包含非正则子集，例如所有串包含等量 a/b 的子集。

同态同样是单向推理：L 正则会导致 $h(L)$ 正则，所以 $h(L)$ 非正则能否定 L 正则；但 $h(L)$ 正则不能反推 L 正则，因为替换可能把难结构抹掉。

2. L04：四类判定问题

来源：L04 p.34–44；对应 #L04-04、#L04-05、#L04-06。

所谓给定正则语言，通常是给定它的 DFA、NFA、正则表达式或正则文法等有限表示。以下算法可以先转成 DFA，再在有限图上工作。

2.1 成员问题：一个串是否合法

输入语言表示和具体字符串 w；从初态按 w 的字符逐个转移，读完检查是否在终态。固定 DFA 时，时间与 $\lvert w\rvert$ 成正比。空串的检查是“不走任何边，直接看初态是否接受”。

2.2 空性问题：是否一个合法串都没有

从初态做图搜索。只要任意终态可达，就存在一条路径，其边标签拼起来就是被接受的字符串；反过来，如果存在被接受的串，它的运行必定是一条到终态的路径。因此

L\ne\varnothing\quad\Longleftrightarrow\quad \text{some accepting state is reachable from the initial state}.

可以用 BFS/DFS，忽略边上具体是什么字母，只看可达性。初态本身是终态时，长度零的路径已经证明非空。

2.3 有限性：不是看到一个环就算无限

先保留同时满足两个条件的状态：从初态可达；从该状态还能走到某个终态。称它们为“可出现在接受路径上的状态”。在这部分图中存在有向环，当且仅当语言无限。

若有这样的环，就能先到环、绕任意多圈、最后走到终态。DFA 每条边消耗一个字符，环非空，所以不同圈数给出不同长度的被接受串，数量无限。

反过来，若没有这种环，所有接受路径都不能重复状态，否则重复部分已经构成有效环。因此接受串长度有上界；有限字母表上，长度有上界的字符串只有有限多个。

补充反例：拒绝所有输入的陷阱状态可以有自环，但它到不了终态。这样的环不会产生任何新的合法串，所以不能据此断言语言无限。若在带空边 NFA 上直接分析，还必须区别只消耗空串的环；先转 DFA 可避开这个问题。

2.4 等价性：两台机器是否在所有串上意见相同

找“恰好一台接受”的字符串集合，也就是对称差：

D=(L_1\cap\overline{L_2})\cup(\overline{L_1}\cap L_2).

若 $D=\varnothing$ ，没有任何分歧，语言相等；若非空，任一成员就是反例。用乘积自动机，终态设成“恰好一个分量接受”，再检查可达性即可。

若用 BFS 保存到每个状态的路径，还能得到一个最短的分歧字符串。这个补充解释了算法不仅能回答“不同”，还能指出“在哪个输入上不同”。

不要比较两台 DFA 的外观或状态数量来判等价：可能只是命名不同，也可能存在冗余状态。

3. L04：泵引理与非正则证明

来源：L04 p.45–100；对应 #L04-07、#L04-08、#L04-09。作业应用见 Q1 详解。

3.1 有限状态为什么记不住任意大的精确计数

先用讲义 p.60 的思路证明等量 a/b 语言非正则。假设有 DFA 识别 $\{a^nb^n:n\ge0\}$ 。无限多个前缀 $a^0,a^1,a^2,\ldots$ 只有有限多个状态可落，因此有 $r\ne s$ 使读完 $a^r$ 和 $a^s$ 后状态相同。

从该状态再读 $b^r$ ，机器不能知道此前读的是哪一个前缀。既然 $a^rb^r$ 必须接受， $a^sb^r$ 也会接受；但两段数量不同，矛盾。

这里“记不住”不是直觉替代证明，而是由重复状态和相同后缀严格推出错误接受。

3.2 泵引理的推导与全部条件

设一个识别正则语言 L 的 DFA 有 p 个状态。读一个长度至少 p 的合法串 w，前 p 次转移产生 p+1 个状态记录，包含初态。取两个相同状态的位置 $r<s\le p$ ，把前 r 个字符设为 x，接下来 $s-r$ 个字符设为 y，其余设为 z。

因此

w=xyz,\quad \lvert xy\rvert=s\le p,\quad \lvert y\rvert=s-r\ge1.

读 x 到某状态 q，读 y 回到 q，再读 z 到终态。重复 y 不改变接着读 z 的起点，所以

xy^iz\in L\qquad(i=0,1,2,\ldots).

此处不是任意切分都保证成立，而是状态重复提供了至少一种切分。讲义 p.57 的“转移数多于状态数”在长度恰好等于 p 时不够准确；严格计数应是“p 次转移对应 p+1 个状态记录”，推导因此覆盖等号。

3.3 量词是一场不能换顺序的游戏

为了证明非正则：对方给任意泵长 p；你挑一个合法长串 w；对方挑任何符合长度限制的 xyz；你再挑 i 把它泵出语言。所有可能的切分都得能被击败。

常见错误有四种：自己定一个具体 p；选的 w 原本不在语言里；只攻击一个切分；把“这次没攻击成功”当成正则证明。

泵引理是必要条件。要证明正则，应实际构造 DFA/NFA/正则表达式，或用封闭性；不能由“看起来都能泵”得出结论。

3.4 等量、回文与不等式：锁住一个区块

例题（L04 Example 4.7 · p.77）

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

公式按讲义重排。假设正则，令 p 为泵长，选 $w=a^pb^p$ 。任意合法切分的 $y=a^t$ ， $1\le t\le p$ ，因为前 p 个字符全是 a。取 $i=2$ 得 $a^{p+t}b^p$ ，数量不等，离开语言。因此不存在能对所有 i 成功的切分。

例题（L04 Example 4.8 · p.84）

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

公式按讲义重排。按后续页使用包含两个不同字母 a、b 的字母表。为避免 w 重名，半串改称 u，完整见证串选 $v=a^pb^pb^pa^p$ ，它是 u 与反转 u 的拼接，其中 $u=a^pb^p$ 。

前 p 位全为 a，所以任意泵段为 $a^t$ 。泵大一次得到 $a^{p+t}b^{2p}a^p$ 。从左数第 $p+1$ 位为 a，从右数第 $p+1$ 位为 b，不是回文，矛盾。只有一个字母的情形则不同：偶数长度串正则，不能忽略字母表至少有两个字符的前提。

为什么 p.90 的全 a 见证串 $a^{2p}$ 不好？当 $p\ge2$ ，对方可以选 $y=aa$ ，泵任意次数后仍是偶数长度的全 a 回文。一个策略对小 p 有效，不足以打败任意 p。

例题（L04 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^pb^{p+1}$ ，原来 a 比 b 少一个。任意 $y=a^t$ ，泵 $i=2$ 后 a 数变成 $p+t\ge p+1$ ，不再严格少于 b。因此失败。这里不要求原语言的所有串都分块排列；只需我们选择的这个分块串是其中成员即可。

3.5 交替块：不能擅自假定 y 只有一个字符或一个块

例题（L04 Example 4.10 · p.92）

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

公式按讲义重排。选 $w=(ab)^{p+1}a^p$ ，满足 $n=p+1>p=k$ 。由于 $\lvert xy\rvert\le p$ ，y 完全在前面的交替区内。取 $i=0$ 。

讲义用很短的 y 举例，完整证明必须覆盖任意长度：

若 $\lvert y\rvert=2r$ 为偶数， $r\ge1$ ，删掉一段偶数长度的交替片段会保留交替相位，结果为 $(ab)^{p+1-r}a^p$ 。剩余块数 $p+1-r\le p$ ，不满足块数严格大于尾部 a 数。
若 $\lvert y\rvert$ 为奇数且 x 为空，删除后串以 b 开头，直接违反形状。
若 $\lvert y\rvert$ 为奇数且 x 非空，删除连接点两侧原本相距偶数个位置，因此字母相同，出现 aa 或 bb。该连接点后还有交替区中的 b：因为删段结束不晚于第 p 位，而交替区长度为 $2p+2$ 。所以 aa 不能被解释为合法的“末尾全 a 段”，bb 更不可能合法。

两类都离开 L，覆盖所有切分，故非正则。这里补全的是原页略去的分类论证，不把讲义举例的切分当成全部切分。

3.6 稀疏长度：把泵后长度夹在相邻合法值之间

例题（L04 Example 4.11 · p.93）

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

公式按讲义重排。选 $w=a^{p^2}$ ，任意泵段为 $a^t$ ， $1\le t\le p$ 。采用泵大 $i=2$ ：

p^2<p^2+t\le p^2+p<p^2+2p+1=(p+1)^2.

长度严格位于相邻平方数之间，因此非成员，矛盾。这个版本对所有 $p\ge1$ 成立。

原页边界说明：讲义选 $i=0$ 并写 $p^2-t>(p-1)^2$ 。当 $p=1,t=1$ 时这变成 $0>0$ ，不成立。可以先把泵长增大到至少 2，再使用讲义的泵小证明；上面改用泵大避免额外边界讨论。没有改动原课件。

HW3 Q1(2) 的 $a^{3^n}$ 正是这个思路的迁移：合法长度换成 $3^p$ 与 $3^{p+1}$ ，泵量仍至多 p。详解已给出所有不等式。

3.7 两个计数之和：直接泵或用同态

例题（L04 Example 4.12 · p.94）

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

公式按讲义重排。取 $a^pb^pc^{2p}$ ，任意泵段是前面 t 个 a，泵小后前两段总数变成 $2p-t$ ，c 数仍为 $2p$ ，违反等式。

另一条课内方法是取同态 $h(a)=a,h(b)=a,h(c)=c$ 。有

h(L)=\{a^{n+k}c^{n+k}:n,k\ge0\}=\{a^rc^r:r\ge0\}.

等式右向左需要解释：每个 $r\ge0$ 都可由 $n=r,k=0$ 得到。右边就是已知非正则的等量双段语言，仅更换了字母。若 L 正则，h(L) 必正则，矛盾。

3.8 “不相等”反而要求泵到相等：阶乘的用途

例题（L04 Example 4.13 · p.95）

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

公式按讲义重排。要泵出这个语言，必须让两段最终相等；简单加一次不一定刚好补齐差值。所以选

w=a^{p!}b^{(p+1)!}.

因为 $p!<(p+1)!$ ，w 合法；前 p 个字符全是 a，因此 $y=a^t$ ， $1\le t\le p$ 。泵 i 次后 a 数为 $p!+(i-1)t$ 。要让它等于 b 数，解方程：

\begin{aligned} p!+(i-1)t&=(p+1)!,\\ (i-1)t&=p\cdot p!,\\ i&=1+\frac{p\cdot p!}{t}. \end{aligned}

为什么这确实是允许的整数 i？因为 $1\le t\le p$ ，t 是 p! 的一个因子，所以分式为整数，且 i 为正。于是可以精确泵到相等，离开语言。这里 i 依赖对方选择的 t，完全符合量词顺序。

也可用封闭性更短地证明：令正则语言 $R=a^\ast b^\ast$ ，若 L 正则，则 $R\setminus L=\{a^nb^n:n\ge0\}$ 正则，矛盾。注意是相对于 R 取差，不是把整个字母表上的补集直接当成等量双段语言；补集中还有形状不对的串。

3.9 质数长度：构造一个合数

例题（L04 p.100）

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

公式按讲义重排。令 p 为泵长，取质数 $q\ge\max(p,2)$ ，选择 $a^q$ ；必须选择质数 q，不能假定泵长 p 本身为质数。

任意 $y=a^t$ ， $1\le t\le p$ 。令 $i=q+1$ ，长度变成

q+(i-1)t=q+qt=q(t+1).

两个因子均至少 2，所以是合数，泵后不在 L。此题依靠质数的因子性质，不需要知道相邻质数间隔。

3.10 结尾小测，两问都做完

题面（L04 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$ 。

(c) 整除语言。 令 p 为泵长，选 $w=a^{p+1}b^{p+1}$ 。原比例等于 1，所以合法。任意合法切分有 $y=a^t$ 、 $1\le t\le p$ 。取 $i=0$ ，新比例为

0<\frac{p+1-t}{p+1}<1.

它不可能是整数，矛盾。注意分子至少为 1，所以完整覆盖边界。

原答案缺口：p.103 选 $a^pb^p$ 后直接取 $i=0$ 。若 $t=p$ ，删完 a 后比例为 0，是整数，在允许 $n=0$ 时没有离开语言。用 $p+1$ 的见证串可以无条件避开这点；若另行约定 $n>0$ ，原边界串被排除，但原页没有明确写出这个约定。

(e) 双边不等式。 沿 p.103 选 $w=a^pb^{p+1}$ 。有 $p\le p+1\le2p$ ，对 $p\ge1$ 都成立。任意 $y=a^t$ ，取 $i=3$ ，泵后 a 数为 $p+2t$ ，b 数仍为 $p+1$ 。由于 $t\ge1$ ，有 $p+2t>p+1$ ，违反 a 数不超过 b 数。因此非正则。

为什么这里 i=2 不保证有效？当 t=1 时会泵到 a/b 都为 $p+1$ ，仍满足条件。i=3 才统一跨过边界。选另一个边界见证 $a^pb^{2p}$ 再泵小也能证明，但上述解法保留了讲义的选择。

4. L05：文法如何用递归生成结构

来源：L05 p.3–21；对应 #L05-01、#L05-02、#L05-03。

4.1 从 regular 到 context-free

L04 已证明等量双段和回文不能靠有限状态机识别。L05 的新方法是递归规则：每次在中间保留一个“未完成的子任务”，并在两边生成需要配对的字符。不同递归层数对应任意大的计数。

上下文无关语言 CFL 是能够由某个 CFG 恰好生成的语言。所有正则语言都是 CFL，但有些 CFL 非正则，例如 $\{a^nb^n:n\ge0\}$ 。所以“证明非正则”和“构造 CFG”完全可以针对同一个语言同时成立。

L05 p.5 还预告 CFL 与带栈的下推自动机有关。此处只需知道栈可保存任意多的待匹配信息；其正式构造是后续内容，不是本次作业的先修要求。

4.2 CFG 的定义与推导记号

文法 $G=(V,T,S,P)$ 包含变量 V、终结符 T、开始变量 S 与产生式 P，其中 V 与 T 不相交。CFG 的每条规则为

A\to\alpha,\qquad A\in V,\quad\alpha\in(V\cup T)^\ast.

即左侧恰好一个变量，右侧可以是任意有限混合串，包括空串。无论 A 出现在句型的什么位置，都可按规则替换，所以叫上下文无关。

$u\Rightarrow v$ 表示使用一条规则做一次替换； $u\Rightarrow^\ast v$ 表示零次或多次替换。文法生成的语言是

L(G)=\{w\in T^\ast:S\Rightarrow^\ast w\}.

必须最后全是终结符，才算语言里的字符串。诸如 aaSbb 还包含变量，只是句型 sentential form。

普通 CFG 可有多个变量出现在右侧，例如 $S\to AB$ 。线性文法要求每条规则右侧最多一个变量；正则文法进一步限制变量的位置，例如右线性规则只在最右侧保留变量。因此正则文法属于线性文法，线性文法属于 CFG，但逆向一般不成立。混合左右线性的规则不能自动称为正则文法。

4.3 配对递归：等量双段

讲义文法（L05 p.10–12）

p.10 $S\to aSb$

$S\to\lambda$

公式按讲义重排，后文用 $\varepsilon$ 写空串。递归 r 次后：

S\Rightarrow^\ast a^rSb^r\Rightarrow a^rb^r.

每一步在左右同时各添一个字符，计数保持相等；停止时删掉中间 S。所有生成串都具有该形式；反过来目标为 n 对时递归 n 次即可。因此语言恰好为 $\{a^nb^n:n\ge0\}$ 。

若要至少一对，把停止规则改为 $S\to ab$ ；此时递归 r 次最终产生 r+1 对。HW3 Q2 正在使用这一点。

4.4 镜像递归：偶回文

讲义文法（L05 Example 5.1 · p.13–15）

p.13 $S\to aSa$

$S\to bSb$

$S\to\lambda$

公式按讲义重排。每次左右加入同一个字符，中心最后为空，所以长度为偶数且关于中心镜像。

原页例子：

S\Rightarrow aSa\Rightarrow abSba\Rightarrow abba.

设递归依次选择的外层字符为 $c_1,c_2,\ldots,c_n$ ，最后得到 $c_1c_2\cdots c_nc_n\cdots c_2c_1=uu^R$ ，故不会多生成。对任何偶回文，首尾字符相同，剥去首尾后还是偶回文，反复剥到空串即可反向得到推导，故不会少生成。

补充变化：若还允许 $S\to a$ 和 $S\to b$ ，就能以单个字符为中心生成奇回文；这属于改变目标语言后的构造，不是原页的文法。

4.5 多变量线性文法：把一轮循环合起来

讲义文法（L05 Example 5.2 · p.16–17）

p.16 $S\to abB$

$A\to aaBb$

$B\to bbAa$

$A\to\lambda$

公式按讲义重排。不要靠长例串猜规律；跟踪同一个变量的一轮展开：

B\Rightarrow bbAa\Rightarrow bbaaBb a.

最后一项中空格仅用于看清结构，也就是 $bbaaBba$ 。所以每次让 B 返回 B，左侧加 bbaa、右侧加 ba。终止时用 $B\Rightarrow bbAa\Rightarrow bba$ 。

因此做 n 轮后：

\begin{aligned} S&\Rightarrow abB\\ &\Rightarrow^\ast ab(bbaa)^nB(ba)^n\\ &\Rightarrow^\ast ab(bbaa)^nbba(ba)^n. \end{aligned}

n=0 得 abbba，n=1 得 abbbaabbaba，与 p.16 的完整推导终点一致。由于唯一递归选择就是 A 返回 B 或终止，因此这个表达式描述全部可能，不只是抽样得到的规律。

4.6 不等数量：把语言拆成两个方向

讲义题目（L05 Example 5.3 · p.18）

p.18 The language $L=\{a^nb^m:n\ne m\}$ is context-free.

公式按讲义重排。拆成 $n>m$ 和 $n<m$ ，再分别表达“多余部分 + 配对部分”。讲义文法为

\begin{aligned} S&\to AS_1\mid S_1B,\\ S_1&\to aS_1b\mid\varepsilon,\\ A&\to aA\mid a,\\ B&\to bB\mid b. \end{aligned}

$S_1$ 生成等量对。A 生成至少一个 a，放在配对段前面，保证 a 严格更多；B 生成至少一个 b，放在配对段后面，保证 b 严格更多。

完备性也能按差值构造：若 $n>m$ ，令 A 生成 $n-m$ 个 a， $S_1$ 生成 m 对；若 $n<m$ ，令 $S_1$ 生成 n 对，B 生成 $m-n$ 个 b。两个差值都严格正，所以 A/B 的基例恰好正确。

此语言刚在 L04 被证明非正则，现在却有 CFG，正好显示两个语言类别的区别。文法右侧 AS1 含两个变量，所以这套文法不是线性文法；仅凭这点不能断言该语言不存在另一套线性文法。

4.7 括号匹配：等量还不够，所有前缀都要合法

讲义文法（L05 Example 5.4 · p.19–21）

p.19 $S\to aSb$

$S\to SS$

$S\to\lambda$

公式按讲义重排。把 a 看作左括号，b 看作右括号。三条规则分别做嵌套、并列、空结构。

目标条件是总数相等，并且任意前缀 v 都满足 $n_a(v)\ge n_b(v)$ 。例如 abba 总数相等，但前缀 abb 中右括号更多，已经提前关闭了不存在的括号，因此不合法。

原页给出的 abab 可以推导为

S\Rightarrow SS\Rightarrow aSbS\Rightarrow abS \Rightarrow abaSb\Rightarrow abab.

为什么规则不会生成非法括号？空串合法；给合法串外套一对括号，内部前缀余额先多 1，不会变负；拼接两个合法串，第一段结束余额归零，第二段再从零开始，也不负。因此按推导结构归纳，所有生成串合法。

为什么所有合法括号都能生成？非空合法串必以 a 开头。找到余额第一次回到 0 的位置，那里是匹配这个 a 的 b，原串可写成 $aubv$ ，其中 u、v 都是更短的合法括号串。对 u、v 递归构造，通过 $S\Rightarrow SS\Rightarrow aSbS$ 接起来即可。这个“首次回零”的分解解释了嵌套加拼接为什么足够。

只有 $S\to aSb\mid\varepsilon$ 时，只能生成完全嵌套的串 aaabbb 一类，不能生成 abab；新增 SS 才能表达并列结构。

4.8 CFG 构造的正确性检查清单

构造时先给每个变量明确职责，再写最小合法串作为停止规则，然后决定一层递归增加什么。写完检查两方向：每条规则是否保持目标结构，任意目标串能否按这些规则拆开。

“文法能生成几个正确例子”不能代替语言相等证明；也要检验空串、最短串、参数为零或一、参数独立还是相等、字母顺序和额外生成。HW3 Q2 与 Q3 的详解均执行了这套检查。

5. L05：推导顺序、句型与树

来源：L05 p.22–38；对应 #L05-04、#L05-05。

5.1 为什么要规定最左与最右

句型有多个变量时，可以按不同先后展开。最左推导每一步展开当前最左变量，最右推导每一步展开当前最右变量；“最左/最右”描述位置，不描述应该选哪条产生式。

讲义文法与目标（L05 p.22–23）

p.22 $S\to AB$

$A\to aaA\mid\lambda$

$B\to Bb\mid\lambda$

公式按讲义重排。A 生成偶数个 a，B 生成任意多个 b，所以 $L(G)=\{a^{2n}b^m:n,m\ge0\}$ 。原页对 aab 的两种推导是：

\begin{aligned} S&\Rightarrow AB\Rightarrow aaAB\Rightarrow aaB \Rightarrow aaBb\Rightarrow aab,\\ S&\Rightarrow AB\Rightarrow ABb\Rightarrow Ab \Rightarrow aaAb\Rightarrow aab. \end{aligned}

第一条先完成 A，再完成 B；第二条先完成 B，再完成 A。两条都让 A 使用一次递归再收尾、B 使用一次递归再收尾，所以它们对应同一棵树。不能凭这两条不同顺序就说文法有歧义。

5.2 更长推导如何逐步检查

讲义文法与目标（L05 Example 5.5 · p.24）

p.24 $S\to aAB$

$A\to bBb$

$B\to A\mid\lambda$

公式按讲义重排，目标串为原页的 abbbb。最左推导：

S\Rightarrow aAB\Rightarrow abBbB\Rightarrow abAbB \Rightarrow abbBbbB\Rightarrow abbbbB\Rightarrow abbbb.

中间的 B 先变成 A，A 再外套一对 b；最后两次分别删掉当前最左的 B。最右推导则先处理原先最右边的 B：

S\Rightarrow aAB\Rightarrow aA\Rightarrow abBb \Rightarrow abAb\Rightarrow abbBbb\Rightarrow abbbb.

做题可逐步圈出下一次应展开的变量，尤其不要把终结符当成可改写的变量。

5.3 一棵推导树记录什么

完整推导树是一棵有序树：根标开始变量；内部节点标变量；若节点 A 的孩子从左到右为 $X_1,\ldots,X_r$ ，文法中必须有规则 $A\to X_1\cdots X_r$ ；叶子全是终结符或空串标记。若使用空产生式，空串叶子是该节点唯一孩子。

从左到右读叶子，再去掉空串标记，得到树的 yield，也就是生成的字符串。“有序”不能省：交换孩子会改变字符顺序。

部分推导树尚未完成，叶子允许有变量；若根为 S，其叶序就是一个句型。比如 S 已展开为 AB，A 再展开为 aaA 后，叶序是 aaAB，不是最终语言成员。

L05 p.37 的对应关系：每个 $w\in L(G)$ 都有生成它的完整树；每棵完整树的 yield 都属于 $L(G)$ 。不同的普通推导顺序可能描述同一棵树；固定为最左推导后，一棵树对应唯一的最左展开顺序。这为下一节的歧义证据提供了基础。

6. L05：从“生成”反过来做“解析”

来源：L05 p.40–56；对应 #L05-06、#L05-07。

生成的问题是：有规则 G，能产生哪些串？解析 parsing 的输入则是规则 G 和具体终结符串 w，要判断是否属于语言，并在属于时找出推导或语法树。

6.1 穷举解析：按推导步数逐层搜索

讲义例题（L05 Example 5.7 · p.43）

p.43 $S\to SS\mid aSb\mid bSa\mid\lambda$

Find derivation of $aabb$ .

公式按讲义重排。只枚举最左推导已足够，因为每个完整树都有一条最左推导。第一层从 S 选规则，得到 SS、aSb、bSa、空串。第二层继续展开最左变量；沿着 aSb 分支，选 $S\to aSb$ 得 aaSbb。第三层选空规则得 aabb，找到答案。

S\Rightarrow aSb\Rightarrow aaSbb\Rightarrow aabb.

按层搜索的好处是：若存在某个有限步数的推导，最终一定会搜到。但对于非成员，搜索树可能无限大，永远找不到，也永远无法宣布“已经搜尽”。例如 SS 可不断增生，空规则又可缩短，使“中间长度暂时很长”不一定意味着不能回到目标长度。

因此“所有成员最终能找到推导”不等于“对所有输入都会停止”。普通的无界穷举不能直接称为完整判定算法。

6.2 没有空规则和单位规则，为什么可以给搜索设上界

空产生式是 $A\to\varepsilon$ ；单位产生式是 $A\to B$ ，B 为单个变量。排除这两种规则后，每一步要么：

右侧长度至少 2，使当前句型总长度至少增加 1；
右侧只有一个终结符，使变量变为终结符，总长度不变，但终结符数量增加 1。

设目标串长度为 N。成功推导中句型长度不能超过 N，因为之后没有空规则让它缩短；终结符数量也不能超过 N，因为终结符不能被改写掉。

从初始长度 1 出发，长度增长步最多 N−1 次；不增长度但生成终结符的步最多 N 次。所以任何成功推导至多 $2N-1$ 步，用讲义较松的上界 $2N$ 就足够。目标为空串时，在没有空规则的 CFG 中不可能生成，可立即拒绝。

这就是 L05 p.49–50 给出的终止理由。注意 $A\to a$ 不增长长度，因此不能把所有规则都说成“每一步长度至少加一”；那个说法只适用于 p.48 的特定改写例子。

6.3 能停机不等于高效

若有 R 条产生式，固定展开最左变量后，每层最多 R 个分支。搜索深度约 2N，就可能检查

R+R^2+\cdots+R^{2N}

个候选。这是指数增长，目标稍长就很昂贵。讲义 p.52 给了指数级上界；此处重点是“对固定文法，指数在输入长度 N 上”。

p.53 预告一般 CFG 可用 CYK 做三次时间量级的成员解析；固定文法时通常记为 $O(N^3)$ 。具体范式转换与动态规划在后续讲，不是本讲已经展开的步骤。

6.4 s-grammar：让每一步都不用猜

L05 p.54 定义 simple grammar：每条规则都是 $A\to a\alpha$ ，a 是一个终结符， $\alpha\in V^\ast$ 是仅由变量组成的串；同一个决策对 $(A,a)$ 至多出现一次。

于是解析时只需要看“当前最左变量 A”和“下一个输入字符 a”，就知道唯一可能使用的规则。无规则就拒绝；有规则就消费 a，再把变量后缀列入待完成任务。输入结束和任务结束必须同时发生，才接受。

讲义文法（L05 Example 5.9 · p.55）

p.55 $S\to aS$

$S\to bSS$

$S\to c$

公式按讲义重排。原页例串 abcc 的唯一最左推导为

S\Rightarrow aS\Rightarrow abSS\Rightarrow abcS\Rightarrow abcc.

下一字符 a 要求第一条，b 要求第二条，c 要求第三条。若再加入 $S\to aSS$ ，则当前变量 S 和输入 a 对应两种规则，不再是 s-grammar，即使每条规则的外形都以终结符开头。

原页“unique derivation”在解析语境下应理解为唯一最左推导/唯一语法树；包含多个变量时，任意顺序的展开仍可能有不同写法。不要把这句话理解成“任何展开顺序只有一种”。

固定文法中每一步恰好消耗一个字符，变量替换的最大长度是常数，因此解析时间是 $O(N)$ 。s-grammar 是 CFG 的受限类型，不代表所有 CFG 都能改成 s-grammar。HW3 Q3 已展示一例可以转换的语言及逐步转换理由。

7. L05：歧义、优先级与固有歧义

来源：L05 p.57–79；对应 #L05-08、#L05-09、#L05-10。

7.1 歧义是存在一个反例，无歧义则要求所有串

G 有歧义，意味着存在一个 $w\in L(G)$ 有至少两棵不同推导树，等价于存在两条不同最左推导，或两条不同最右推导。只找一个见证就够了。

G 无歧义，意味着每个语言成员的推导树都唯一。试过几个串没有发现两棵树，不能证明这个全称结论。

讲义例题（L05 Example 5.10 · p.58）

p.58 $S\to aSb$

$S\to SS$

$S\to\lambda$

$aabb$

公式按讲义重排。原页以 aabb 为例。两条最左推导可以写为

S\Rightarrow aSb\Rightarrow aaSbb\Rightarrow aabb,

以及

S\Rightarrow SS\Rightarrow S\Rightarrow aSb \Rightarrow aaSbb\Rightarrow aabb.

第二条先把左侧 S 变为空串，右侧 S 再展开；根规则是 SS，第一条根规则是 aSb，所以对应不同的树，即便最后产出的字符相同。

这也说明 Q4 可以从最简单的子结构入手： $S\to SS\mid d$ 已足够让 ddd 出现两种分组，不必强行把所有产生式都用一次。

7.2 算术歧义：同样的字符，不同的计算顺序

讲义文法与串（L05 Example 5.11 · p.59–63）

p.59 $E\to E+E\mid E\ast E\mid(E)\mid a$

$a+a\ast a$

公式按讲义重排。两条最左推导分别是

\begin{aligned} E&\Rightarrow E+E\Rightarrow a+E\Rightarrow a+E\ast E \Rightarrow a+a\ast E\Rightarrow a+a\ast a,\\ E&\Rightarrow E\ast E\Rightarrow E+E\ast E\Rightarrow a+E\ast E \Rightarrow a+a\ast E\Rightarrow a+a\ast a. \end{aligned}

第一条根上选择加法，结构为 $a+(a\ast a)$ ；第二条根上选择乘法，结构为 $(a+a)\ast a$ 。根不同意味着树不同，而叶序相同。

讲义 p.66–68 代入 a=2，第一种得到 $2+2\cdot2=6$ ，第二种得到 $(2+2)\cdot2=8$ 。歧义不只是画图不同，它可能改变程序的实际结果。

7.3 用 E/T/F 分层表达优先级与结合性

L05 p.71 的改写文法为

\begin{aligned} E&\to E+T\mid T,\\ T&\to T\ast F\mid F,\\ F&\to(E)\mid a. \end{aligned}

E 是表达式，由若干项相加；T 是项，由若干因子相乘；F 是因子，可以是原子 a 或括号中的表达式。

为什么乘法优先？加法节点连接的是已经完整形成的 T；一个 T 内可以含乘法，但不能出现未被括号包住的顶层加法。因此在 $a+a\ast a$ 中，右边必须先构成乘法项，再与左项相加。

为什么同级左结合？规则 $E\to E+T$ 让左边还能继续生成加法，右边只是一个 T。所以 a+a+a 只能在顶层按 $(a+a)+a$ 组织；若右边要再出现加法，就必须通过因子的括号显式包起来。

原页串的最左推导为

\begin{aligned} E&\Rightarrow E+T\Rightarrow T+T\Rightarrow F+T \Rightarrow a+T\\ &\Rightarrow a+T\ast F\Rightarrow a+F\ast F \Rightarrow a+a\ast F\Rightarrow a+a\ast a. \end{aligned}

无歧义的理由可以递归看：表达式按括号深度为零的加号分项，项按深度为零的乘号分因子，分割位置由输入唯一确定；左递归固定相同层级的分组；因子是 a 或一对包围完整表达式的括号。这不只是“没有找到反例”。

7.4 悬空 else：else 到底属于哪个 if

讲义 L05 p.75–76 给出的串为：

if expr1 then if expr2 then stmt1 else stmt2

它可以解释成外层 if 的 then 部分包含完整 if-else；也可以解释成外层 if 有 else，而内层 if 没有 else。两种结构分别是：

if expr1 then (if expr2 then stmt1 else stmt2)
if expr1 then (if expr2 then stmt1) else stmt2

括号是解释结构用的，不是原输入。补充：语言设计可以规定 else 匹配最近未匹配的 if，或通过区分已匹配/未匹配语句的文法落实这种规则。仅靠人阅读时“通常会这样理解”，不能让原来有两棵树的文法自动变为无歧义。

7.5 文法歧义与语言固有歧义不是一回事

一套文法有歧义，可能通过重新设计规则去掉，如 E/T/F 的例子。语言固有歧义则是更强的性质：所有生成该语言的 CFG 都有歧义。

L05 p.77–78 给出经典语言

L=\{a^nb^nc^m:n,m\ge0\}\cup\{a^nb^mc^m:n,m\ge0\}.

左支要求 a/b 相等，右支要求 b/c 相等。交叠处 $a^rb^rc^r$ 能从两条分支生成，因此讲义所列的“先选分支”文法确实有歧义。

但“两个分支有重叠”只证明这套文法有歧义，不能单独证明所有等价文法都如此。该语言固有歧义是讲义引用的进一步结论，p.78 指向外部证明；课件没有给出排除所有文法的完整证明，本文不把双分支例子伪装成那个证明。理解其定义和证据强弱，已覆盖本讲讲授范围。

7.6 讲义最后一道歧义练习

题面（L05 Exercise 5.3.6 · p.79）

p.79 Show that the following grammar is ambiguous.

$S\to AB\mid aaB$

$A\to a\mid Aa$

$B\to b$

公式按原题重排。选同一个串 aab：

S\Rightarrow aaB\Rightarrow aab,

以及

S\Rightarrow AB\Rightarrow AaB\Rightarrow aaB\Rightarrow aab.

两条都是最左推导，根的选择不同，所以证明有歧义。题目没有要求枚举全部成员，也没有要求修改文法。

8. L05：这些概念怎样进入编译器

来源：L05 p.81–89；对应 #L05-11。

p.82 的流程图已视觉核对：源文件进入 lexer；lexer 输出 token 流给 parser；parser 输出 parse tree 给 codegen；codegen 输出 object code。图中的三段任务需要分开理解。

词法分析 lexer 把字符序列切成 token，例如数字、标识符、运算符。语法分析 parser 根据 CFG，把 token 按结构组织成树。代码生成 codegen 再根据结构确定运算与指令的顺序。该图是教学上的简化流程，不表示真实编译器没有其他检查或优化阶段。

讲义 p.85–87 以 10 + 2 * 5 示意：正确的树先将 2 与 5 组成乘法子树，再与 10 相加。对应指令为先 mult a, 2, 5，再 add b, 10, a，得到 20。变量 a、b 在此是保存中间结果的位置，不是前面形式语言中的输入字母。

BNF（Backus–Naur Form）是书写文法的常用记法，::= 作用类似产生式箭头，尖括号内通常表示非终结符，竖线表示选择。例如 p.88 的

<expr> ::= <term> | <expr> + <term>
<term> ::= <factor> | <term> * <factor>

与前面的 E/T/F 分层表达相同思想。LL、LR 是可高效解析的文法类别，本页只概述其线性解析特征，并没有要求在本讲完成分析表构造。

最后区分语法 syntax 与语义 semantics：一句话结构符合文法，不代表变量类型、名字绑定或实际意义都正确。讲义 p.89 的字符变量与小数赋值示例意在提示这种差别；是否允许转换取决于具体语言的类型规则，不能只看 CFG 判定。

p.89 还列出文法歧义与 CFG 等价等困难问题。不要把 L04 的 DFA 对称差判空算法原样搬到任意 CFG；其依据是正则语言的补与交封闭及有限状态表示。这里学习目标是识别两类模型的能力与算法边界，不把“找到一个歧义见证容易”误解成“任何输入文法都能用试例判定”。

原页图表与演算补全

以下补足原讲义的具体机器、树结构和演算；与前面的主题解释一起即可独立学习。

L04 P1

把原图变成可执行的两张输入表（p.16–18）

p.16 用 s 表示左侧初态，f 表示中间终态，d 表示右侧死状态。转移为 s 读 a 留 s、读 b 到 f；f 读 a 或 b 均到 d；d 读任意字母留 d。原机终态为 {f}，补机终态为 {s,d}。每个串读完只有一个位置，所以逐个翻转接受性确实覆盖全集。

p.17–18 的乘积构造依赖下面两张原始表。这样不必对着箭头猜：

第一台状态	读0	读1	接受
A（初态）	B	A	是
B	C	A	是
C	C	C	否

第二台状态	读0	读1	接受
X（初态）	Y	X	否
Y	Y	Z	否
Z	Y	X	是

可达表中每格都可由它们独立算出，例如 CZ 读1得到 CX。去掉 AY、BX、BZ 的依据是不可达，不是这些状态“不接受”。

L04 P2

四个算法各自在有限什么（p.36–44）

问题	具体输入	有限搜索对象	返回“是”的条件
成员	DFA 与一个串 w	w 的每个位置	读完停终态
语言为空	DFA	初态可达状态	可达集合与终态集无交
语言有限	DFA	既可达又可到终态的子图	其中没有有向环
两语言相等	两台同字母表 DFA	可达状态对	每一对的终态资格一致

“空”与“不含空串”完全不同。只接受 a 的机器不含空串，但语言不空；只接受空串的机器语言也不空，而且有限。若有 n 个有用状态且有用子图无环，接受路径不可能重复状态，长度至多 n−1；有限字母表上长度有统一上界，才推出串的总数有限。

L04 P3

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

状态	读 a	读 b
q1（初态）	q2	q1
q2	q3	q2
q3	q2	q4
q4（终态）	q3	q4

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 大于所有成员长度，就没有满足长度门槛的成员，条件空真。于是“无限”不是证明正则性的办法，亦不能把“有限语言没有长串可泵”误判为违反引理。

L04 P4

将原解的指数变化统一记账（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。因此

xy^iz=a^{r+ik+m-r-k}b^{m+1} =a^{m+(i-1)k}b^{m+1}.

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

L05 原页补全

四元组的每个位置（p.7–8）： $V$ 是可替换的变量集合， $T$ 是最终输出的终结符集合，二者不相交； $S\in V$ 是开始变量； $P$ 是有限产生式集合。 $\Rightarrow$ 表示恰好应用一次规则， $\Rightarrow^{\ast}$ 表示零次或多次；只要还留变量，就只是句型，不能算已经生成的语言成员。

例如有 $A\to aAb$ ，在 xAy 中允许变成 xaAby，在 BAA 中也能选任意一个 A 展开；规则的适用性不检查 A 的邻居。这正是“上下文无关”的含义，不是说整串结构没有关系。p.6 的右线性 $S\to abS\mid a$ 和左线性 $S\to Aab,A\to Aab\mid B,B\to a$ 都满足左侧单变量，因此都是 CFG。

L05 原页补全

p.31–32 的完整树也可用下列缩进完整表示；同一层从左到右的顺序就是原图孩子顺序：

S
├─ A
│  ├─ a
│  ├─ a
│  └─ A
│     └─ λ
└─ B
   ├─ B
   │  └─ λ
   └─ b

忽略内部变量并按叶子从左到右读，正是 aaλλb。p.36 的另一棵完整树则为 S(a,A(b,B(λ),b),B(A(b,B(λ),b)))，括号内列有序孩子。它把四个 b 分到左右两个子树各两个，与 p.24 把四个 b 全放左边不同。

L05 原页补全

p.44 的第二轮候选完整展开：固定最左变量后，SS 分别变成 SSS、aSbS、bSaS、S；aSb 分别变成 aSSb、aaSbb、abSab、ab。第一支 bSa 从首字符 b 起就与目标 aabb 冲突，可以剪去；第二轮的 bSaS 同理，abSab 的第二个终结符已经是 b，而目标第二位要 a，也可剪去。这就是 p.45 留下的 SSS、aSbS、S、aSSb、aaSbb。然后 aaSbb 用空规则得到 aabb。剪枝只利用已经固定的终结符次序，不把暂时未展开的 S 当作空串。

L05 原页补全

p.77–78 展示的文法不能省去：

\begin{aligned} S&\to S_1\mid S_2,\\ S_1&\to S_1c\mid A,& A&\to aAb\mid\lambda,\\ S_2&\to aS_2\mid B,& B&\to bBc\mid\lambda. \end{aligned}

第一支先留下任意个尾部 c，再由 A 配对 a、b；第二支先留下任意个头部 a，再由 B 配对 b、c。对 abc，两条最左推导分别为 $S\Rightarrow S_1\Rightarrow S_1c\Rightarrow Ac\Rightarrow aAbc\Rightarrow abc$ 与 $S\Rightarrow S_2\Rightarrow aS_2\Rightarrow aB\Rightarrow abBc\Rightarrow abc$ 。这具体落实了课件的两树见证；课件将更强的固有歧义定理归于 Harrison（1978），该归因在这里按课件保留，并非本次独立查阅该著作。

L05 原页补全

p.81 的程序与指令示意全文：

源程序                         指令示意
v = 5;                         Add v,v,0
if (v>5)                       cmp v,5
    x = 12 + v;                jmplt ELSE
while (x !=3) {                THEN:
    x = x - 3;                   add x,12,v
    v = 10;                    ELSE:
}                              WHILE:
......                         cmp x,3
                               ...

这一页是阶段关系示意，并非完整可执行编译结果。特别是右侧首行并不能在一般指令语义下实现左侧 v=5，跳转与循环也不完整；应从中理解“高级语句被拆为计算、比较、跳转”，不能拿它当逐条正确的汇编模板。p.82 图底部列 Ken Thompson（UNIX/grep/vi 中的正则表达式）、Eric E. Schmidt、Mike Lesk（lex）、Stephen C. Johnson（yacc），这些是原课件的工具背景标注，不是本次独立历史考证。

L05 原页补全

p.84 的全部规则（保留演示文法的原形）：

PROGRAM → STMT_LIST
STMT_LIST → STMT ; STMT_LIST | STMT ;
STMT → EXPR | IF_STMT | WHILE_STMT | { STMT_LIST }
EXPR → EXPR + EXPR | EXPR - EXPR | ID
IF_STMT → if ( EXPR ) then STMT
        | if ( EXPR ) then STMT else STMT
WHILE_STMT → while ( EXPR ) do STMT

分号、括号、花括号和关键字是终结符；PROGRAM 等大写名是变量；ID 表示标识符记号。列表没有空规则，因此至少一条语句且最后也带分号；递归选第一条可继续加语句，选第二条结束。它只演示列出的语言片段，不能据此声称 p.81 中的赋值、比较等全部已被定义。

L05 原页补全

p.88 的两个 BNF 例子为：

<expr> ::= <term> | <expr> + <term>
<term> ::= <factor> | <term> * <factor>

它们对应上一部分 E、T 两层；本页没有再给 factor 的完整规则，应沿用上一部分的“括号表达式或原子”的解释理解示例。p.89 还明确提出“两份 CFG 是否等价”的问题，并用 Char a, b, c; c = 3.2; 说明语法与语义的差别。是否允许把3.2赋给字符类型，要由具体语言的类型及转换规则决定，不能只凭这两行断言每种语言都拒绝。

9. 学完后应能自己完成的检查

以下是自编理解检查，非原题。先停下来口头回答，再看紧接着的答案。

为什么 DFA 有 p 个状态，读 p 个字符就够保证状态重复？
泵引理中能不能自己指定 y 为第一个 a？
一个 DFA 有自环，语言一定无限吗？
$A\to aABb$ 是 CFG 规则吗？是 s-grammar 规则吗？
一条最左推导与一条最右推导得到相同串，足够证明歧义吗？
写出非正则语言的 CFG，会与非正则证明矛盾吗？

答案与解释：1. 包括初态，共 p+1 次状态记录。2. 不能只检查自己指定的切分；必须覆盖任意合法切分。3. 不一定，环必须从初态可达且能到终态。4. 是 CFG，因为左侧是单变量；不是 s-grammar，因为首终结符后还出现终结符 b。5. 不够，可能只是同一棵树的不同展开顺序。6. 不矛盾，CFG 能描述的语言严格多于正则语言。

10. 完整性对账与原课件边界

课件范围	主题	本文位置 / 对应作业
L04 p.3–16	并、拼接、星、反转、补	第 1 节，含构造条件
L04 p.17–28	乘积、交、差、集合恒等式	第 1 节，含原例状态表和执行
L04 p.29–32	同态	第 1 节，含两例替换
L04 p.34–44	成员、空性、有限性、等价	第 2 节，含算法及成立理由
L04 p.46–75	有限记忆、鸽巢原理、泵引理、量词	第 3 节 / HW3 Q1 前置知识
L04 p.77–100	全部所列非正则例题、误区	第 3 节 / HW3 Q1(1)–(2)
L04 p.102–103	整除、不等式小测	第 3 节，均给完整证明
L05 p.3–21	CFG/CFL、线性、配对、回文、括号	第 4 节 / HW3 Q2–Q3
L05 p.22–38	最左/最右、句型、完整/部分树	第 5 节 / HW3 Q4
L05 p.40–53	穷举解析、终止与复杂度、CYK 预告	第 6 节
L05 p.54–56	s-grammar、预测与线性解析	第 6 节 / HW3 Q3 的完整轨迹
L05 p.57–79	歧义、优先级、else、固有歧义、练习	第 7 节 / HW3 Q4
L05 p.81–89	编译流程、BNF、LL/LR 概述、语法语义	第 8 节

原标题页、Outline、过渡、Questions 页没有独立知识点，不重复堆入正文。L04 p.54–59 的示例 DFA、长串运行，以及 L05 的树、产生式和搜索过程已补入上方“原页图表与演算补全”；重复动画合并为可逐步阅读的演算。本文没有声称逐页重绘全部课件图形。

本次对照已有课程索引的 L04-01 至 L04-09、L05-01 至 L05-11，共 20 个概念条目，均有对应解释。新作业的解答、自取例子和对讲义证明的补严不新增为讲义课程索引条目，旧条目与原课件未改写。

已明确区分的细节：L04 p.57 应计 p+1 个状态记录；p.92 的 y 需覆盖任意交替子串；p.93 泵小证明需处理 p=1；p.103(c) 需处理 a 被完全删掉；L05 p.55 的唯一推导指规范解析顺序；p.77–78 的双分支树不能独自证明固有歧义。正文逐项给出推理或说明课件未提供的证明范围。

来源与证据

L04-正则语言性质-资料包.pdf（本地课件）：已读取全部 103 页的可提取文本，另视觉核对 p.18、p.42、p.67、p.93、p.102–103；关键定义、运算符与小测题面据原件校核。
L05-上下文无关文法-资料包.pdf（本地课件）：已读取全部 90 页的可提取文本，另视觉核对 p.54、p.82、p.90；其余树图未逐张视觉重绘，正文采用可核的产生式与独立推导。
HW3_2026.pdf（本地课件）：p.1 全文与图像已读，题目对应关系以此 2026 版为准。
已查阅本课程课程索引索引的 L04/L05 条目作覆盖对账；知识与页码以本次读取的原课件为准。教材 Ch.4、Ch.5 是课件所标章节，本次未另读教材或外部网页。
考试证据：读了 HW3_2026.pdf；未识别用途的 PDF：无。
未读：HW03-手写作答-202510211114.pdf、HW03-2025T1-参考解答.pdf、HW03-2025T1-题目.pdf（往年材料，不作为本次题目或答案依据）。

2026-10-13 独立学习版：以上内容已与本轮 L04、L05 分段笔记同步，完整文字与关键图表核对范围见相应分段笔记。

乘积状态	读 0	读 1	交接受	差接受
AX	BY	AX	否	是
BY	CY	AZ	否	是
AZ	BY	AX	是	否
CY	CY	CZ	否	否
CZ	CY	CX	否	否
CX	CY	CX	否	否

乘积状态	读 0	读 1	交接受	差接受
AX	BY	AX	否	是
BY	CY	AZ	否	是
AZ	BY	AX	是	否
CY	CY	CZ	否	否
CZ	CY	CX	否	否
CX	CY	CX	否	否

乘积状态	读 0	读 1	交接受	差接受
AX	BY	AX	否	是
BY	CY	AZ	否	是
AZ	BY	AX	是	否
CY	CY	CZ	否	否
CZ	CY	CX	否	否
CX	CY	CX	否	否