形式语言与自动机第三章课后题精讲：上下文无关文法、二义性与泵引理

1. 为什么第三章的课后题值得单独拎出来讲

形式语言与自动机这门课，很多人学到第三章会突然感觉“画风变了”。前两章还在跟有限状态机、正则表达式打交道，画个状态图、写个正则就能应付；到了第三章，突然冒出来一堆语法推导、派生树、二义性判断、文法化简的题目，很多人第一反应是“这到底在考什么”。

我当年带过几届学生的习题课，也帮不少同学做过考前突击。一个很明显的规律是：第三章的课后题，是整个课程里“投入产出比”最高的一部分。原因很简单——第三章的核心是上下文无关文法（CFG），而CFG是后面下推自动机、语法分析、编译原理的根基。你第三章的题做明白了，后面第四章的PDA构造、第五章的语法分析算法，基本就是顺水推舟；第三章糊弄过去，后面就是一路塌方。

但问题在于，第三章的课后题往往没有标准答案流传，或者流传的答案只给结果不给过程。比如“判断下列文法是否二义性”，答案写个“是”或“否”，你看了等于没看。真正有价值的是：怎么一步步推导出这个结论的，中间用了什么判定技巧，遇到类似题目怎么迁移。

这篇内容就是冲着这个来的。我会把第三章课后题里最典型的几类题型拆开，从“题目在考什么”到“手把手推导过程”再到“我当年踩过的坑”，全部讲透。适合正在学这门课、被课后题卡住的同学，也适合想重新捡起这块知识的从业者。全文不堆术语，能用大白话讲清楚的地方绝不用定义绕人。

2. 第三章课后题的题型地图与核心考点

2.1 先搞清楚第三章到底在讲什么

不同教材的章节划分略有差异，但“第三章”在绝大多数形式语言与自动机教材里，对应的都是上下文无关文法这一块。核心内容包括：

• 文法的形式定义（四元组G = (V, T, P, S)）
• 推导、最左推导、最右推导
• 派生树（语法树）与二义性
• 文法的化简（消除无用符号、消除ε产生式、消除单位产生式）
• 乔姆斯基范式（CNF）与格雷巴赫范式（GNF）
• 泵引理用于证明语言不是上下文无关的

课后题基本就是围绕这些点出题。我把常见题型整理成一张表，你可以对照自己的作业看看属于哪一类：

这张表你先存着。下面我按题型逐个拆，重点讲那些“答案只给结果、过程全靠悟”的题。

2.2 为什么文法设计题最容易丢分

文法设计题通常是这样的：“构造生成下列语言的CFG：L = {a^i b^j c^k | i = j 或 j = k}”。

很多同学拿到题就开始瞎写产生式，写出来一测发现要么多生成了不该有的串，要么漏掉了某些合法串。根本原因是没有先分析语言的结构。

我的经验是，文法设计题一定要先做三件事：

1. 把语言的“约束条件”翻译成“生成策略”。比如i = j，意味着a和b要“配对”生成，那就需要一个非终结符同时负责生成a和b。
2. 判断约束之间是“或”还是“与”。上面这题是“或”，那就分别构造两个子文法，再用一个开始符号做并集。
3. 验证边界情况。i、j、k是否可以为0？如果可以为0，ε产生式要不要加？

按这个思路，上面那题的解法就清晰了：

S → S1 | S2 S1 → aS1b | C // 负责 i = j 的情况 S2 → bS2c | A // 负责 j = k 的情况 C → cC | ε // 生成任意个c A → aA | ε // 生成任意个a

这里有个细节：S1生成a和b配对后，后面接任意个c；S2生成b和c配对后，前面接任意个a。但这样会有一个重叠问题——当i = j = k时，串会被两个分支同时生成。这在文法设计里是允许的，因为语言是并集，重复生成不影响正确性。但如果你在学二义性，这种“重复生成”恰恰是二义性的来源之一。

注意：文法设计题没有唯一答案。你的文法和参考答案不一样，不代表你错了。关键是用几个典型串测一下，确认它能生成所有合法串、不生成非法串。

2.3 推导与派生树：看似简单，实则暗藏规范陷阱

“给出串的最左推导和最右推导，并画出派生树”——这是送分题，但每年都有人在这里丢分。丢分点通常不是不会，而是不规范。

最左推导的定义是：每一步都替换当前句型中最左边的非终结符。最右推导则是最右边的。听起来简单，但手写的时候很容易“跳步”或者“替换错位置”。

我建议的做法是：每写一步，先把当前句型抄下来，标出所有非终结符的位置，然后圈出你要替换的那个。比如文法：

S → AB A → aA | a B → bB | b

串“aab”的最左推导：

S ⇒ AB ⇒ aAB ⇒ aaB ⇒ aab

每一步我都确认了替换的是最左边的非终结符。第三步从aaB到aab，替换的是B，此时句型aaB里只有B一个非终结符，所以没问题。

派生树的画法也有讲究。派生树的叶子从左到右读出来必须等于原串，内部节点是产生式左部，子节点是右部。很多人画树的时候把顺序搞反，或者把ε产生式的叶子漏掉。如果产生式里有ε，派生树上要画一个ε的叶子节点，不能省略。

提示：考试时如果时间紧，派生树可以先画结构再补标签，但一定要保证叶子顺序和串一致。我见过太多人树画得漂亮，叶子读出来是“aba”而不是“aab”。

3. 二义性判断：从“看感觉”到“有方法”

3.1 二义性到底在说什么

二义性（ambiguity）的定义是：一个文法存在某个串，它有两棵不同的派生树。注意，是“存在某个串”，不是“所有串”。所以判断一个文法是否二义，你只需要找到一个反例串就行；但要证明一个文法不是二义的，那就难了，通常需要分析文法的结构。

课后题里常见的问法有两种：

• “判断下列文法是否二义性”——这种题通常答案是“是”，因为找反例比证明无二义容易得多。
• “证明下列文法是二义的”——直接找反例串和两棵派生树。

3.2 找反例串的实战套路

以经典文法为例：

E → E + E | E * E | (E) | id

这是表达式文法，显然是二义的。反例串用“id + id * id”就行。两棵派生树的区别在于：一棵先算加法（*优先级高），一棵先算乘法（+优先级高）。

但很多同学卡在“怎么把两棵树画出来”。我的建议是，不要一上来就画完整的树，先写两个不同的最左推导，推导不同，派生树必然不同。

推导一（先展开左边的E）：

E ⇒ E + E ⇒ id + E ⇒ id + E * E ⇒ id + id * E ⇒ id + id * id

推导二（先展开右边的E）：

E ⇒ E * E ⇒ E + E * E ⇒ id + E * E ⇒ id + id * E ⇒ id + id * id

两个推导都是最左推导，但步骤不同，说明派生树不同，二义性得证。

这里有个技巧：找二义性反例时，优先选那些“运算符优先级”或“结合性”有歧义的串。比如加法乘法混合、减法连续出现（a - b - c）、if-else嵌套等。这些串天然容易产生两种解析方式。

3.3 一个容易被忽略的坑：二义性不是文法的“错”

很多同学觉得“二义性文法就是坏文法”，其实不是。二义性文法在描述语言时完全合法，只是它生成的串有多个解析。在实际编译器中，我们通常会用优先级和结合性规则来“消歧”，而不是强行把文法改成无二义的。

但课后题不管这些，它就是要你判断。所以做题时不要想太多“这个文法好不好”，只看定义。

注意：如果题目问“该文法生成的语言是否是二义性语言”，那是另一个概念。语言层面的二义性是指该语言不存在无二义文法，这比文法二义性难证明得多。课后题一般不会考到这么深，但你要能区分这两个问法。

4. 文法化简：顺序错了，全盘皆输

4.1 化简的三板斧及其正确顺序

文法化简通常包括三步：

1. 消除无用符号（无用非终结符和不可达符号）
2. 消除ε产生式
3. 消除单位产生式

这三步的顺序不能随便换。我见过太多人先消ε再消无用符号，结果消完ε之后又产生了新的无用符号，还得再来一遍。

正确的顺序是：先消ε产生式，再消单位产生式，最后消无用符号。为什么？因为消ε和消单位产生式都可能产生新的无用符号或新的ε产生式，所以要把“产生新问题”的步骤放在前面，把“清理现场”的步骤放在最后。

4.2 消除ε产生式的具体操作

消除ε产生式的核心思路是：对于每个形如A → ε的产生式，找出所有“可能为ε”的非终结符，然后在其他产生式中“可选地”去掉这些非终结符。

举个例子：

S → AB A → aA | ε B → bB | ε

A和B都可以推出ε。那么S → AB中，A和B都可以“消失”，所以S也可以推出ε。我们要把所有“可选消失”的组合都列出来：

S → AB | A | B | ε A → aA | a B → bB | b

注意，A → aA | ε变成A → aA | a，因为原来A可以推出ε，现在把ε去掉，但原来用ε的地方要用“不出现”来补偿。B同理。

这里有个细节：如果开始符号S本身可以推出ε，而语言中又必须保留ε，那就要加一个新的开始符号S' → S | ε。如果语言中不需要ε，那就直接去掉。

4.3 消除单位产生式的坑

单位产生式是形如A → B的产生式，右边只有一个非终结符。消除的方法是：对于每个A，找出所有A能“单位推导”到的非终结符，然后把那些非终结符的产生式“复制”给A。

比如：

S → A | B A → a B → b

S → A和S → B是单位产生式。消除后：

S → a | b A → a B → b

看起来简单，但坑在于：单位产生式可能形成环。比如A → B，B → A。这时候你要小心，不能无限复制。处理方法是先找出所有单位对，然后按传递闭包来复制。

我当年做这题的时候，就因为没处理环，复制了三遍还没完，最后发现A和B互相指向，直接把它们的所有非单位产生式合并就行。

提示：消除单位产生式后，一定要检查是否还有单位产生式残留。有时候复制过程中会引入新的单位产生式，需要再扫一遍。

5. 范式转换：CNF和GNF的机械流程与手算技巧

5.1 乔姆斯基范式（CNF）的转换步骤

CNF的要求是：所有产生式形如A → BC或A → a。转换步骤：

1. 消除ε产生式和单位产生式（前面讲过）
2. 消除右部长度大于2的产生式，引入新非终结符
3. 消除右部长度等于2但含终结符的产生式，把终结符替换成新非终结符

举个例子：

S → aSb | ε

先消ε（假设语言需要保留ε，加S' → S | ε）：

S' → S | ε S → aSb | ab

然后处理S → aSb，右部长度3，引入新非终结符：

S → ASB | AB A → a B → b

再处理S → ASB，右部长度3，继续拆：

S → AX | AB X → SB A → a B → b

现在所有产生式要么是A → a，要么是A → BC。但注意S' → S是单位产生式，还要消掉：

S' → AX | AB | ε S → AX | AB X → SB A → a B → b

这样才符合CNF。

5.2 手算CNF的省时技巧

CNF转换是纯机械操作，但手算容易出错。我的经验是：

• 先列一张表，把所有产生式按右部长度分类：长度1（终结符）、长度1（非终结符，即单位产生式）、长度2、长度≥3。
• 长度≥3的优先处理，因为拆完之后可能产生新的长度2产生式。
• 终结符替换放在最后，因为替换后会产生新的非终结符，可能影响前面的拆分。

另外，新非终结符的命名要有规律，比如用X1、X2、X3，不要用S、A、B这些已经存在的，避免混淆。

5.3 格雷巴赫范式（GNF）为什么让人头疼

GNF的要求更严：所有产生式形如A → aα，其中a是终结符，α是非终结符串（可以为空）。GNF的转换比CNF复杂得多，课后题如果考GNF，通常是给一个比较简单的文法。

GNF转换的核心是“消除左递归”和“替换”。步骤大致是：

1. 把非终结符排序A1, A2, ..., An
2. 对于每个Ai，确保Ai → Ajα中j > i，如果不是，用Aj的产生式替换
3. 消除直接左递归
4. 最后把所有产生式整理成A → aα的形式

这个过程手算非常繁琐，我建议考试时如果遇到GNF题，先判断文法是否简单到可以“一眼看出”结果。如果太复杂，先把前面的步骤写清楚，能拿多少分拿多少分。

注意：GNF转换中，左递归的消除公式是A → Aα | β变成A → βA'，A' → αA' | ε。但GNF不允许ε产生式，所以最后还要消ε。这个顺序不能乱。

6. 泵引理：证明“不是上下文无关”的终极武器

6.1 泵引理在第三章的地位

泵引理是用来证明某个语言不是上下文无关的。课后题里通常会给一个看起来像CFL但实际不是的语言，让你用泵引理证明。

泵引理的内容是：如果L是CFL，那么存在常数p，使得L中任何长度≥p的串s都可以分成s = uvxyz，满足：

1. |vxy| ≤ p
2. |vy| ≥ 1
3. 对所有i ≥ 0，uv^i xy^i z ∈ L

注意，这里的“泵”是同时泵v和y，而且v和y可以分别泵不同的次数，但必须是同一个i。

6.2 用泵引理证明的实战流程

以经典例子L = {a^n b^n c^n | n ≥ 0}为例。证明它不是CFL：

1. 假设L是CFL，取泵引理常数p。
2. 选串s = a^p b^p c^p，长度3p ≥ p。
3. 根据泵引理，s = uvxyz，|vxy| ≤ p，|vy| ≥ 1。
4. 因为|vxy| ≤ p，所以vxy不可能同时包含a、b、c三种字符（因为a和c之间隔了至少p个b）。
5. 分情况讨论：
   • 如果vxy只包含a和b，那么泵之后a和b的数量变了，c不变，串不再属于L。
   • 如果vxy只包含b和c，同理。
   • 如果vxy只包含一种字符，泵之后该字符数量变化，其他不变，也不属于L。
6. 所有情况都矛盾，所以L不是CFL。

这个证明的关键在于选对串和分情况讨论完整。很多同学选串的时候选了个“a^p b^p c^p”，但分情况时漏了“vxy只包含b”的情况，导致证明不完整。

6.3 选串的技巧与常见错误

选串是泵引理证明中最需要经验的一步。我的经验是：

• 选那些“约束最紧”的串。比如L = {a^i b^j c^k | i < j < k}，选a^p b^{p+1} c^{p+2}就比选a^p b^p c^p好，因为前者更容易在泵之后违反不等式。
• 让vxy的范围尽可能小。因为|vxy| ≤ p，如果串的结构能让vxy只能落在某个局部，分情况就少。
• 避免选太对称的串。对称的串有时候泵了之后还是合法的，比如L = {ww | w ∈ {a,b}*}，选a^p b^p a^p b^p，泵中间部分可能还是合法的。这种语言需要用更复杂的技巧，课后题一般不会考。

常见错误包括：分情况不完整、泵的时候只泵v不泵y、忘记|vy| ≥ 1的条件。我建议做完之后检查一遍：你的分情况是否覆盖了vxy所有可能的字符组成？每种情况下泵之后是否真的违反了L的定义？

提示：泵引理证明是“反证法”，所以最后一定要写“与泵引理矛盾，假设不成立，L不是CFL”。这句话不写，扣分。

7. 我踩过的坑与考前突击建议

7.1 那些年我在第三章课后题上栽的跟头

第一个坑：文法设计题不验证。我曾经设计了一个文法，觉得“看起来没问题”就交了，结果老师用一个空串就测出我漏了ε的情况。从那以后，我每次设计完文法，至少测五个串：空串、单字符、最短非空串、最长串、边界串。

第二个坑：二义性判断只凭感觉。有些文法看起来“应该”是二义的，但实际上不是。比如S → aSb | ab，这个文法生成a^n b^n，它是无二义的。因为每个串只有一种推导方式。判断二义性不能靠直觉，要么找到两棵不同的派生树，要么分析文法的结构证明唯一性。

第三个坑：化简顺序搞反。先消了无用符号，再消ε产生式，结果消完ε之后又出现了新的无用符号。这个坑我踩了不止一次，后来养成了“先消ε，再消单位，最后消无用”的固定顺序。

第四个坑：CNF转换时新非终结符命名冲突。用了S作为新非终结符，结果和原来的S混淆，产生式写乱了。后来我改用X1、X2、X3，再也没出过问题。

7.2 考前突击的优先级排序

如果你时间紧，第三章课后题按这个优先级复习：

1. 文法设计：必考，而且分值高。重点练“i = j 或 j = k”这类带约束的语言。
2. 二义性判断：找反例串的方法要熟练，两棵派生树要会画。
3. 文法化简：顺序记牢，消ε和消单位的操作要能默写。
4. CNF转换：机械流程，练两三道题就能上手。
5. 泵引理：如果考，通常是压轴题。把经典例子（a^n b^n c^n）的证明过程背下来，考试时套用。
6. GNF：如果老师没重点讲，可以放最后。考到的概率相对低。

7.3 一个实用的自检清单

做完一道第三章课后题，问自己这几个问题：

• 文法设计题：我测过空串和边界串了吗？有没有多生成或漏生成？
• 推导题：每一步替换的是最左/最右非终结符吗？派生树的叶子顺序对吗？
• 二义性题：我找到的是两棵不同的派生树，还是同一个推导的两种写法？
• 化简题：顺序对吗？消完之后有没有新的无用符号？
• CNF题：所有产生式都符合A → BC或A → a吗？有没有残留的单位产生式？
• 泵引理题：分情况完整吗？泵之后真的违反语言定义了吗？

这个清单你可以在每次做完题后过一遍，能避免大部分低级错误。

最后说一句，第三章的课后题，做一遍是不够的。我当年把同一道题做了三遍：第一遍对着答案理解，第二遍合上答案自己写，第三遍隔一周再写一次。第三遍还能写对，才是真的会了。形式语言这门课，手感比理解更重要，而手感是靠重复练出来的。