简介这份PDF面向计算机专业学生与编译原理自学者聚焦蒋立源《编译原理》第三版第三章的习题与解答帮助读者攻克文法、状态转换图、NFA、DFA与正规式等核心考点。资源包共1个文件为PDF格式大小约2.97MB内容涵盖右线性文法构造、状态转换矩阵分析、NFA确定化与最小化、含ε动作的NFA处理、正规式描述语言及3型文法推导等典型题型。每道题均给出完整解题过程与答案如习题3-1的右线性文法构造、3-4的DFA最小化分划步骤、3-6的正规式推导等便于对照教材同步练习。目前已有1919人学习下载适合需要巩固第三章知识点、备考或查漏补缺的读者使用。1. 从一份习题答案说起为什么第三章是编译原理的分水岭很多人学编译原理前两章还跟得上一到第三章就开始掉队。词法分析里的正规式、NFA、DFA、右线性文法这几个概念单独看都懂但一放到题目里——给你一个状态转换图让你反推文法或者给你一个带 ε 动作的 NFA 让你确定化再最小化——就不知道从哪下手了。这份《蒋立源编译原理第三版第三章习题与答案(修改后).pdf》针对的正是这个卡点它把 3-1 到 3-8 共八道题的完整推导过程整理成了可对照的答案覆盖右线性文法构造、状态转换图与矩阵互转、NFA 确定化、DFA 最小化、正规式与 NFA 互构这几类核心题型。适合正在跟这门课、准备期末或考研复试的读者也适合已经工作但想回头把自动机理论这块补扎实的人。下面我不按答案顺序复述而是按「拿到题怎么想、参数怎么定、哪里容易翻车」的路子拆一遍。2. 右线性文法与状态转换图3-1 到 3-3 的互推逻辑2.1 右线性文法的形式约束与 3-1 的等价改造右线性文法3 型文法的核心约束只有一条每个产生式的右部非终结符只能出现在最右端形如 A → aB 或 A → a。这条约束决定了它和有限自动机是一一对应的——文法的非终结符就是自动机的状态产生式就是状态转移边。3-1 给的原文法产生式写得比较乱有A → fUT、U → faU|a、T → fbT|b、B → fcB|c这样的形式。要把它改造成标准右线性文法关键是识别出哪些符号是终结符、哪些是非终结符然后把产生式右部整理成「终结符 至多一个非终结符」的结构。答案给出的等价右线性文法是A → aA | bB B → bB | cC | c C → cC | c这里有个容易忽略的点原文法里出现的f、U、T这些符号在等价改造后可能被吸收或重命名。改造的依据是语言等价——两个文法产生的串集合必须完全相同。3-1 对应的语言是L {a^m b^n c^i | m,n,i ≥ 1}也就是至少一个 a、至少一个 b、至少一个 c 按顺序排列。注意等价改造不是逐条产生式对应翻译而是先确定语言再构造满足右线性约束的新文法。很多人在这一步试图直接改写原产生式结果改出来的文法要么多生成串要么少生成串。2.2 从状态转换图反推文法3-2 的四个小问怎么答3-2 给了一张状态转换图要求做四件事写右线性文法、找最短输入串、列 4 个可接受串、列 4 个被拒绝串。这四问其实是一条链——文法写对了后面三问就是顺带的事。从状态转换图写右线性文法的步骤给每个状态起一个非终结符名字初态对应开始符号。对每条从状态 X 到状态 Y、标记为 a 的转移边写产生式X → aY。对每个终态 Z如果它有到自身的转移或需要终止补上Z → ε或对应的终止产生式。答案给出的文法是G[A]: A → 0D | 0A | 1C | 0B | 1C终态处理上E → 0B | 1C。最短输入串是011可接受的串如0110、0011、000011、00110被拒绝的串如0111、1011、1100、1001。这里有个实操技巧找最短输入串时从初态出发找一条到终态的最短路径路径上的标记连起来就是答案。列可接受串时在最短串基础上加自环或绕路列被拒绝串时故意在某个状态走一条不存在的边或者走到非终态就停。2.3 状态转换矩阵与 3 型文法的双向转换3-3 的四组矩阵3-3 给了四组状态转换矩阵i 到 iv每组要求画状态转换图、写 3 型文法、用自然语言描述识别特征。这题的信息量在于矩阵、图、文法三者是同一事物的三种表示能自由转换才算真正理解。以矩阵 (i) 为例初态 S、终态 B转移表如下状态abSASAABBBB从矩阵读文法每一行对应一个非终结符的产生式。S 行S → aA | bSA 行A → aA | bBB 行B → aB | bB且 B 是终态补B → ε。状态转换图就是把矩阵画成有向图每个状态一个圆圈转移边标字母。自然语言描述识别特征这块答案给的是「以任意个 b 开头中间有任意个 a跟一个 b还可以有一个由 a、b 组成的任意字符串」。这种描述没有标准答案但必须覆盖三个要素开头允许什么、中间必须出现什么、结尾允许什么。提示3-3 的四组矩阵里(ii) 和 (iv) 的终态集有多个状态写文法时每个终态都要补终止产生式漏一个就会导致语言描述出错。3. NFA 确定化与 DFA 最小化3-4 和 3-5 的手工推导流程3.1 子集构造法确定化从 NFA 到 DFA 的状态命名3-4 要求将 NFA 确定化并最小化共四组子题。确定化用的是子集构造法核心操作是从初态出发对每个输入符号求闭包得到新的状态集合给每个集合起一个新名字直到不再产生新集合。以 3-4 的第 (1) 组为例确定化过程如下初始状态集合[S] 对输入 a[S,A] 对输入 b[A,B] 对输入 a[S,A]已存在 对输入 b[B] ...答案里给各状态重新命名为[S]1、[S,A]2、[A,B]3、[B]4终态集是{3,4}。确定化后的状态转换矩阵状态ab123223343444这一步最容易翻车的地方是闭包计算。如果 NFA 里有 ε 转移求闭包时要把 ε 能到达的所有状态都纳入集合。3-4 的 NFA 没有 ε 动作所以闭包就是状态本身但 3-5 的 NFA 带 ε 动作闭包计算就复杂得多。3.2 DFA 最小化分划法的终止条件与状态合并确定化得到 DFA 后状态数可能不是最少的需要最小化。最小化用分划法先把状态分成终态和非终态两个子集然后不断细分直到每个子集内的状态对任何输入都转移到相同的子集。3-4 第 (1) 组的最小化过程初始分划Π₀ {1,2}, {3,4} 考察 {1,2}{2} 在 b 下到 3{1} 在 b 下到 3但 {2} 在 a 下到 2{1} 在 a 下到 2暂时不可区分 再考察 {3,4}{3} 在 a 下到 4{4} 在 a 下到 4{3} 在 b 下到 3{4} 在 b 下到 4可区分 最终分划{1}, {2}, {3}, {4}当所有子集都不能再分裂时最小化结束。每个子集选一个代表状态把其他状态的入边重定向到代表状态。注意分划法的终止条件是「本次分划结果与上次相同」不是「每个子集只有一个状态」。有些 DFA 最小化后仍然有多个状态在同一子集这是正常的。3.3 带 ε 动作的 NFA 确定化3-5 的闭包计算差异3-5 的 NFA 带 ε 动作确定化时每一步都要先求 ε 闭包。以第 (1) 组为例ε-closure({S}) {S, B, C} 对输入 a从 {S,B,C} 出发a 能到达的状态是 {A}再求 ε 闭包得 {A} 对输入 b从 {S,B,C} 出发b 能到达的状态是 {B,C}再求 ε 闭包得 {B,C} ...答案给的重命名是[S,B,C]1、[A]2、[B,C]3、[C]4终态集{1,3,4}。这里的关键区别是不带 ε 的 NFA 确定化时新状态集合就是转移目标本身带 ε 的 NFA 确定化时新状态集合是转移目标的 ε 闭包。手工推导时建议画一张表每行是一个新状态集合每列是一个输入符号表格填完后统一命名。这样不容易漏状态也方便检查是否所有转移都覆盖到了。4. 正规式与 NFA 互构3-6 到 3-8 的方程法与 Thompson 构造4.1 用方程组求解正规式3-6 的代数法3-6 给文法G[S]: S → aA, A → aA | bB, B → bB | cC | c, C → cC | c要求用正规式描述它产生的语言。这题用方程组法最直接把每个非终结符看成一个未知数产生式看成方程S aA A aA bB B bB cC c C cC c然后从最内层往外解。C 的方程C cC c符合X xX y的形式解为C c*c。代入 B 得B bB c*c解为B b*c*c。代入 A 得A aA bb*c*c解为A a*bb*c*c。最后代入 S 得S aa*bb*c*c。答案写的是a*ab*bc*c和上面的推导等价只是提取公因式的方式不同。这里用到的论断是方程X xX y的解为X x*y这是正规式方程的基本结论。提示方程组法解正规式时代入顺序要从最内层开始先解只含自身和终结符的方程再逐层往外代。如果方程之间有循环依赖需要先用 Arden 引理消解。4.2 Thompson 构造法3-7 的两个正规式转 NFA3-7 要求构造与正规式((0*|1)(1*0))*和b|a(aa*b)*b相应的 NFA。Thompson 构造法的基本规则对单个字符 a构造两个状态一条标记 a 的边。对连接RS把 R 的终态和 S 的初态合并。对选择R|S新建初态和终态分别连到 R 和 S 的初态/终态。对闭包R*新建初态和终态加 ε 边形成循环。以((0*|1)(1*0))*为例从内到外逐步构造0*两个状态0 自环 0*|1并联加 ε 边 (0*|1)(1*0)串联 ((0*|1)(1*0))*加闭包答案图 3-7-(1) 和 3-7-(2) 给出了完整的 NFA 图。手工画的时候建议先用纸笔按规则一步步展开不要跳步否则很容易漏 ε 边或接错状态。4.3 3-8 的完整链路正规式 → NFA → DFA → 最小化3-8 是第三章的综合题给正规式(a|b)*(aa|bb)(a|b)*要求构造相应的 DFA。完整链路是用 Thompson 构造法从正规式构造 NFA。用子集构造法将 NFA 确定化。用分划法将 DFA 最小化。答案给出的确定化后状态重命名是[S,3,1]S、[3,1,5]A、[3,1,6]B、[3,1,5,2,4,Z]C、[3,1,6,2,4,Z]D、[3,1,6,4,Z]E、[3,1,5,4,Z]F终态集{C,D,E,F}。这题的状态数比较多手工推导时容易在闭包计算和状态命名上出错。建议的做法是先列出所有可能的子集给每个子集分配一个编号然后画转移表最后根据转移表画 DFA 图。不要一边算闭包一边画图那样很容易乱。5. 避坑与排查手工推导 NFA/DFA 时的五类翻车现场5.1 闭包漏算 ε 转移现象确定化后的 DFA 状态数比预期少或者某些输入串的接受结果和原 NFA 不一致。原因求 ε 闭包时只算了直接 ε 转移漏掉了多步 ε 转移。比如A →ε B →ε C闭包应该包含 C但只算了 B。解决闭包计算要递归到底直到没有新的状态加入。手工算的时候每加入一个新状态都要检查它是否有 ε 转移。5.2 状态命名冲突现象确定化过程中两个不同的子集被起了同一个名字导致转移表混乱。原因子集构造法产生的新状态集合可能看起来相似比如{S,A}和{S,A,B}手工命名时容易混淆。解决每产生一个新子集先检查是否已存在存在则复用旧名不存在才分配新名。建议用表格记录「子集 → 新名」的映射。5.3 最小化分划过早终止现象最小化后的 DFA 状态数仍然偏多或者合并后的 DFA 接受的语言变了。原因分划过程中只检查了部分输入符号就判断两个状态不可区分导致该分裂的子集没有分裂。解决每次分划时对每个子集内的所有状态对检查所有输入符号下的转移目标是否在同一子集。只要有一对状态在某个输入下转移到不同子集就要分裂。5.4 正规式方程代入顺序错误现象解出的正规式和答案不一致或者方程无法消解。原因代入顺序不对把含有未解未知数的方程代入了另一个含有相同未知数的方程导致循环。解决从最内层开始解先解只含自身和终结符的方程解出后再代入外层方程。如果方程之间有循环依赖先用 Arden 引理消解。5.5 状态转换图与文法不对应现象从状态转换图写出的文法和从状态转换矩阵写出的文法不一致。原因状态转换图漏画了边或者矩阵的某一行填错了。解决图和矩阵要交叉验证。从图读文法后再用文法反推矩阵看是否和原矩阵一致。不一致的地方就是出错的地方。6. 把第三章的推导习惯带到工程里一个检查清单学完第三章的习题真正有价值的不只是会做这几道题而是养成一套手工推导自动机的检查习惯。我自己的做法是每次做完确定化或最小化强制走一遍下面这个清单。检查项具体操作常见问题闭包完整性对每个新状态集合递归检查 ε 转移漏算多步 ε 闭包状态命名唯一性维护「子集 → 新名」映射表不同子集重名转移表覆盖每个状态 × 每个输入符号都有目标漏填转移目标终态集确认检查每个子集是否含原 NFA 终态漏标终态最小化终止条件本次分划与上次相同才停止过早终止语言等价验证用几个典型串测试接受/拒绝只测最短串这个清单看起来简单但我在带人做编译原理实验时发现大部分错误都出在前三项。尤其是闭包完整性手工算的时候很容易漏掉「ε 转移链」的最后一环。还有一个习惯是每做完一道题用 3 到 5 个输入串手工模拟一遍 DFA 的运行过程看接受结果是否符合预期。比如 3-8 的 DFA可以用aa、bb、abab、aabb、abba这几个串测试。如果某个串的接受结果和正规式的直觉不符就回去检查确定化或最小化的步骤。从那以后我每次做自动机推导都会先画转移表再画图最后用典型串验证一遍。这个习惯帮我省了很多返工的时间。希望帮到你。本文还有配套的精品资源点击获取