1. 为什么第三章的课后题值得单独拎出来讲形式语言与自动机这门课很多人学到第三章会突然感觉“画风变了”。前两章还在跟有限状态机、正则表达式打交道画个状态图、写个正则就能应付到了第三章突然冒出来一堆语法推导、派生树、二义性判断、文法化简的题目很多人第一反应是“这到底在考什么”。我当年带过几届学生的习题课也帮不少同学做过考前突击。一个很明显的规律是第三章的课后题是整个课程里“投入产出比”最高的一部分。原因很简单——第三章的核心是上下文无关文法CFG而CFG是后面下推自动机、语法分析、编译原理的根基。你第三章的题做明白了后面第四章的PDA构造、第五章的语法分析算法基本就是顺水推舟第三章糊弄过去后面就是一路塌方。但问题在于第三章的课后题往往没有标准答案流传或者流传的答案只给结果不给过程。比如“判断下列文法是否二义性”答案写个“是”或“否”你看了等于没看。真正有价值的是怎么一步步推导出这个结论的中间用了什么判定技巧遇到类似题目怎么迁移。这篇内容就是冲着这个来的。我会把第三章课后题里最典型的几类题型拆开从“题目在考什么”到“手把手推导过程”再到“我当年踩过的坑”全部讲透。适合正在学这门课、被课后题卡住的同学也适合想重新捡起这块知识的从业者。全文不堆术语能用大白话讲清楚的地方绝不用定义绕人。2. 第三章课后题的题型地图与核心考点2.1 先搞清楚第三章到底在讲什么不同教材的章节划分略有差异但“第三章”在绝大多数形式语言与自动机教材里对应的都是上下文无关文法这一块。核心内容包括文法的形式定义四元组G (V, T, P, S)推导、最左推导、最右推导派生树语法树与二义性文法的化简消除无用符号、消除ε产生式、消除单位产生式乔姆斯基范式CNF与格雷巴赫范式GNF泵引理用于证明语言不是上下文无关的课后题基本就是围绕这些点出题。我把常见题型整理成一张表你可以对照自己的作业看看属于哪一类题型类别典型问法核心考点难度感受文法设计给出语言描述构造CFG对语言结构的理解中等偏难推导与派生树给出文法和串写最左/最右推导画派生树推导过程的规范性基础二义性判断判断文法是否二义或证明某文法二义派生树不唯一难文法化简消除无用符号/ε产生式/单位产生式化简顺序与正确性中等范式转换将文法转为CNF或GNF机械步骤的熟练度中等偏烦泵引理证明证明某语言不是CFL反证法的构造难这张表你先存着。下面我按题型逐个拆重点讲那些“答案只给结果、过程全靠悟”的题。2.2 为什么文法设计题最容易丢分文法设计题通常是这样的“构造生成下列语言的CFGL {a^i b^j c^k | i j 或 j k}”。很多同学拿到题就开始瞎写产生式写出来一测发现要么多生成了不该有的串要么漏掉了某些合法串。根本原因是没有先分析语言的结构。我的经验是文法设计题一定要先做三件事把语言的“约束条件”翻译成“生成策略”。比如i j意味着a和b要“配对”生成那就需要一个非终结符同时负责生成a和b。判断约束之间是“或”还是“与”。上面这题是“或”那就分别构造两个子文法再用一个开始符号做并集。验证边界情况。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配对后后面接任意个cS2生成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”就行。两棵派生树的区别在于一棵先算加法*优先级高一棵先算乘法优先级高。但很多同学卡在“怎么把两棵树画出来”。我的建议是不要一上来就画完整的树先写两个不同的最左推导推导不同派生树必然不同。推导一先展开左边的EE ⇒ E E ⇒ id E ⇒ id E * E ⇒ id id * E ⇒ id id * id推导二先展开右边的EE ⇒ E * E ⇒ E E * E ⇒ id E * E ⇒ id id * E ⇒ id id * id两个推导都是最左推导但步骤不同说明派生树不同二义性得证。这里有个技巧找二义性反例时优先选那些“运算符优先级”或“结合性”有歧义的串。比如加法乘法混合、减法连续出现a - b - c、if-else嵌套等。这些串天然容易产生两种解析方式。3.3 一个容易被忽略的坑二义性不是文法的“错”很多同学觉得“二义性文法就是坏文法”其实不是。二义性文法在描述语言时完全合法只是它生成的串有多个解析。在实际编译器中我们通常会用优先级和结合性规则来“消歧”而不是强行把文法改成无二义的。但课后题不管这些它就是要你判断。所以做题时不要想太多“这个文法好不好”只看定义。注意如果题目问“该文法生成的语言是否是二义性语言”那是另一个概念。语言层面的二义性是指该语言不存在无二义文法这比文法二义性难证明得多。课后题一般不会考到这么深但你要能区分这两个问法。4. 文法化简顺序错了全盘皆输4.1 化简的三板斧及其正确顺序文法化简通常包括三步消除无用符号无用非终结符和不可达符号消除ε产生式消除单位产生式这三步的顺序不能随便换。我见过太多人先消ε再消无用符号结果消完ε之后又产生了新的无用符号还得再来一遍。正确的顺序是先消ε产生式再消单位产生式最后消无用符号。为什么因为消ε和消单位产生式都可能产生新的无用符号或新的ε产生式所以要把“产生新问题”的步骤放在前面把“清理现场”的步骤放在最后。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 → bS → A和S → B是单位产生式。消除后S → a | b A → a B → b看起来简单但坑在于单位产生式可能形成环。比如A → BB → A。这时候你要小心不能无限复制。处理方法是先找出所有单位对然后按传递闭包来复制。我当年做这题的时候就因为没处理环复制了三遍还没完最后发现A和B互相指向直接把它们的所有非单位产生式合并就行。提示消除单位产生式后一定要检查是否还有单位产生式残留。有时候复制过程中会引入新的单位产生式需要再扫一遍。5. 范式转换CNF和GNF的机械流程与手算技巧5.1 乔姆斯基范式CNF的转换步骤CNF的要求是所有产生式形如A → BC或A → a。转换步骤消除ε产生式和单位产生式前面讲过消除右部长度大于2的产生式引入新非终结符消除右部长度等于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转换的核心是“消除左递归”和“替换”。步骤大致是把非终结符排序A1, A2, ..., An对于每个Ai确保Ai → Ajα中j i如果不是用Aj的产生式替换消除直接左递归最后把所有产生式整理成A → aα的形式这个过程手算非常繁琐我建议考试时如果遇到GNF题先判断文法是否简单到可以“一眼看出”结果。如果太复杂先把前面的步骤写清楚能拿多少分拿多少分。注意GNF转换中左递归的消除公式是A → Aα | β变成A → βAA → αA | ε。但GNF不允许ε产生式所以最后还要消ε。这个顺序不能乱。6. 泵引理证明“不是上下文无关”的终极武器6.1 泵引理在第三章的地位泵引理是用来证明某个语言不是上下文无关的。课后题里通常会给一个看起来像CFL但实际不是的语言让你用泵引理证明。泵引理的内容是如果L是CFL那么存在常数p使得L中任何长度≥p的串s都可以分成s uvxyz满足|vxy| ≤ p|vy| ≥ 1对所有i ≥ 0uv^i xy^i z ∈ L注意这里的“泵”是同时泵v和y而且v和y可以分别泵不同的次数但必须是同一个i。6.2 用泵引理证明的实战流程以经典例子L {a^n b^n c^n | n ≥ 0}为例。证明它不是CFL假设L是CFL取泵引理常数p。选串s a^p b^p c^p长度3p ≥ p。根据泵引理s uvxyz|vxy| ≤ p|vy| ≥ 1。因为|vxy| ≤ p所以vxy不可能同时包含a、b、c三种字符因为a和c之间隔了至少p个b。分情况讨论如果vxy只包含a和b那么泵之后a和b的数量变了c不变串不再属于L。如果vxy只包含b和c同理。如果vxy只包含一种字符泵之后该字符数量变化其他不变也不属于L。所有情况都矛盾所以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^{p1} c^{p2}就比选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 考前突击的优先级排序如果你时间紧第三章课后题按这个优先级复习文法设计必考而且分值高。重点练“i j 或 j k”这类带约束的语言。二义性判断找反例串的方法要熟练两棵派生树要会画。文法化简顺序记牢消ε和消单位的操作要能默写。CNF转换机械流程练两三道题就能上手。泵引理如果考通常是压轴题。把经典例子a^n b^n c^n的证明过程背下来考试时套用。GNF如果老师没重点讲可以放最后。考到的概率相对低。7.3 一个实用的自检清单做完一道第三章课后题问自己这几个问题文法设计题我测过空串和边界串了吗有没有多生成或漏生成推导题每一步替换的是最左/最右非终结符吗派生树的叶子顺序对吗二义性题我找到的是两棵不同的派生树还是同一个推导的两种写法化简题顺序对吗消完之后有没有新的无用符号CNF题所有产生式都符合A → BC或A → a吗有没有残留的单位产生式泵引理题分情况完整吗泵之后真的违反语言定义了吗这个清单你可以在每次做完题后过一遍能避免大部分低级错误。最后说一句第三章的课后题做一遍是不够的。我当年把同一道题做了三遍第一遍对着答案理解第二遍合上答案自己写第三遍隔一周再写一次。第三遍还能写对才是真的会了。形式语言这门课手感比理解更重要而手感是靠重复练出来的。