简介：蒋立源《编译原理》第三版第三章习题与答案（修改后）PDF面向高校计算机专业学生和考研备考生，集中讲解右线性文法、NFA与DFA、正规式、状态转换图与状态转换矩阵等核心概念。文件为单个PDF文档（共1个文件），体积仅2.97MB，轻量便于下载和打印，收录习题3-1至3-8的完整题目与参考答案，并附有逐步推导过程，对文法构造、NFA确定化与最小化、带ε动作的NFA转换、DFA构建等易错难点尤其具有参考价值。目前已有1918人学习下载。读者通过逐题演练，可厘清形式语言与自动机之间的联系，掌握状态转换矩阵与文法的对应关系，并学会用正规式描述语言特征，无论日常作业还是期末备考，都能快速定位薄弱环节，为后续词法分析、语法分析和编译器设计打下扎实基础。
1. 编译原理第三章：为什么这章全是文法与自动机转换
把蒋立源《编译原理》第三版第三章从头到尾过一遍，你会发现这章其实只围绕一件事展开：让文法、状态转换图、NFA、DFA、正规式这几种描述语言的方式互相翻译。很多人在词法分析实验里栽跟头，不是概念不懂，而是在“右线性文法怎么等价改写”“NFA确定化之后终态怎么判”“最小化时谁和谁可以合并”这类操作细节上卡住。这一章被吉林大学、哈尔滨工业大学等高校的课件反复引用，也是编译原理面试题里自动机部分的标准素材。这篇笔记就按第三章习题的展开顺序，把子集构造法、DFA分裂最小化以及正规式转DFA的完整步骤拆开讲，备考期末、复试或者刷题的人可以直接对着复现。
2. 右线性文法与状态转换图：从一道题看等价改写
2.1 为什么词法分析只盯着右线性文法
右线性文法的定义很苛刻：每个产生式右侧最多只有一个非终结符，而且它必须出现在最右端。形式化地说，所有产生式只能是A → aB或者A → a（a为终结符，A、B为非终结符）。也有教材允许A → ε。
这个限制看起来让文法表达能力变弱了，但它恰好框定了正则语言的范围。词法分析器要识别的标识符、关键字、数字常量，本质上都是正则语言，不需要嵌套结构，所以右线性文法足够用。这也是为什么第三章先讲它——后面的NFA、DFA、正规式描述的语言集合和右线性文法完全一致，四者互相转换是本章的核心能力。
从状态转换图到右线性文法的转换规则也很机械，可以直接当模板用：
- 每个状态对应一个非终结符，开始状态对应开始符号。
- 图中一条从
A到B、标记为x的边，写成产生式A → xB。 - 终态额外产生一条到空串的产生式，比如
A → ε（有些教材不显式写出，做题时判断串是否接受需要它）。
反过来，从右线性文法画状态转换图就是上述过程的逆操作，每个非终结符画成一个状态，每条产生式画成一条边。
2.2 习题3-1：把非右线性文法改写成等价形式
习题3-1给了一个产生式排版比较混乱的文法，整理后其产生式大致形如：
S → AB A → aU | a U → aU | a B → bT | b T → bT | b注意这里的问题：S → AB右侧出现两个非终结符，不满足右线性文法“至多一个非终结符且在最后”的限制。更明显的问题是这个文法描述的语言是{a^m b^n | m,n ≥ 1}，修改的关键在于去掉中间的非终结符级联，直接让计数逻辑在每个非终结符内部完成。
教材给出的等价右线性文法是：
S → aA A → aA | bB B → bB | cC | c C → cC | c这里S → aA保证开头至少一个a；A → aA | bB表示a可以继续出现，也可以切换到b；B → bB | cC | c同理。改写后的每个产生式右侧都在最右端保留至多一个非终结符，而且语言没有变。
做题时容易漏掉的一点：不要把开始符号S直接写在A → aA这个循环里。S的作用只是“启动”，如果写成S → aS | aB，虽然也是右线性文法，但推出来的串会少掉中间必须经过A的层次约束，语言就变成{a^n b^m}之外的东西了。
2.3 习题3-2：从状态转换图反推右线性文法
习题3-2反过来，给出状态转换图，要求写出右线性文法、指出最短接受串、列出接受和拒绝的串。按前面说的模板操作即可。
题图3-2整理后对应一组产生式（按教材答案的原图结构）：
A → 0D D → 0A | 1C C → 0B | 1C B → 0B | 1C最短输入串的判断方法是在状态图上做广度优先搜索：从开始状态A出发，找一条长度最短、能到达某个终态的路径。答案是011，路径为A → D → C → C，终点落在终态集合中。
接受和拒绝的串可以直接列成对比，方便检查自己对终态判定的理解：
| 类型 | 输入串 | 判定依据 |
|---|---|---|
| 接受 | 011 | 最短路径，结束在终态 |
| 接受 | 0110 | 在011后面追加字符，仍能回到终态 |
| 接受 | 0011 | 前面增加0，进入同一接受路径 |
| 拒绝 | 0111 | 最后一步转移到非终态 |
| 拒绝 | 1011 | 首字符1在开始状态无对应转移 |
| 拒绝 | 1100 | 首字符无转移，直接卡死 |
这里常见的一个误判是只看“能不能走完输入串”而不看“最终停在哪”。NFA或者DFA接受一个串，必须同时满足：输入读完，且当前状态是终态；两者缺一不可。
3. NFA确定化：子集构造法的完整执行细节
3.1 子集构造法要解决什么问题
NFA允许同一个状态读入同一个字符后跳到多个状态，也允许通过ε边不消耗字符地跳转。这给“模拟执行”带来了不确定性：给定输入串，可能有无数条尝试路径，不能简单地按单一路径判断接受与否。
确定化的本质是“把多个可能状态的集合当作DFA的一个状态”。DFA的每个状态对应NFA的一个状态子集，DFA的转移是在这个子集上做并集运算。这个算法叫子集构造法，做题和写代码都用同一个框架：
# 子集构造法：输入 NFA 的状态集、转移函数和开始状态 Dstates = [epsilon_closure({nfa.start})] # DFA 初态 unmarked = {0} # 待处理的状态下标 while unmarked: idx = unmarked.pop() T = Dstates[idx] for ch in alphabet: # 对每个输入符号 U = epsilon_closure(move(T, ch)) # 先求move，再求ε闭包 if U not in Dstates: Dstates.append(U) unmarked.add(len(Dstates) - 1) Dtrans[(idx, ch)] = U # 记录DFA转移move(T, ch)是收集T中所有状态经过一条ch边能到达的状态；epsilon_closure再把其中每个状态经任意多条ε边能到达的状态并进来。顺序不能反，先move后闭包，否则会漏掉“先走字符边、再走ε边”的可能。
3.2 习题3-4(1)：确定化与状态重命名
以习题3-4(1)为例，原始NFA的状态转换矩阵整理后如下：
| NFA状态 | a | b |
|---|---|---|
| S | {S,A} | 空 |
| S,A | {S,A} | {A,B} |
| A,B | {B} | {A,B} |
| B | 空 | {B} |
初态是S，终态是B。子集构造法第一步，求初态的ε闭包，这里没有ε边，所以DFA初态就是{S}。然后逐个处理：
{S}读入a得到{S,A}，读入b得到空集。{S,A}是新状态，入队。{S,A}读入a得{S,A}，读入b得{A,B}。{A,B}读入a得{B}，读入b得{A,B}。{B}读入b得{B}。
重命名后得到DFA状态：1 ={S}，2 ={S,A}，3 ={A,B}，4 ={B}。注意判定DFA终态的方法：只要子集里包含原NFA的终态B，这个DFA状态就是终态。所以3和4是终态。
| DFA状态 | a | b | 是否终态 |
|---|---|---|---|
| 1 | 2 | 空 | 否 |
| 2 | 2 | 3 | 否 |
| 3 | 4 | 3 | 是 |
| 4 | 空 | 4 | 是 |
动手做的时候有两个高频错误：第一，忘记把move的结果再做一次ε闭包；第二，只把“子集恰好等于终态”的状态判为终态，而正确的判据是“子集包含终态”。只要NFA终态在子集里出现，这个DFA状态就必须是终态。
3.3 带ε动作的NFA：先算ε闭包
习题3-5专门练带ε动作的NFA确定化。ε边不消耗输入字符，因此求ε闭包是确定化的前置步骤。闭包计算的实现其实就是图的遍历：
def epsilon_closure(states, eps_table): # states: 初始状态集，例如 {1, 2} # eps_table: 字典，键为状态，值为该状态经ε边直接到达的状态列表 stack = list(states) closure = set(states) while stack: s = stack.pop() for t in eps_table.get(s, []): if t not in closure: closure.add(t) stack.append(t) return closure参数说明：eps_table里只存直接的ε转移边，闭包会沿着这些边反复扩散，直到没有新状态出现。比如状态S有S →ε B、B →ε C，那么epsilon_closure({S})返回{S, B, C}。
习题3-5(1)做完后，DFA初态是包含原NFA初态S的ε闭包{S, B, C}，重命名为1。然后对每个输入符号重复“move + 闭包”。最终DFA终态集是{1, 3, 4}，因为这三个状态对应的子集都包含原NFA终态C。
提示：如果确定化之后发现某个DFA状态没有任何出边，这是正常的。因为原NFA在该子集上对某个输入符号的move结果为空，空集在DFA里通常直接省略不画，但转移表中建议保留一列“空”便于后续最小化时检查区分性。
4. DFA最小化与分裂算法：从习题3-8看正规式到DFA的化简路径
4.1 分裂法最小化的迭代结构
DFA最小化解决的是“状态冗余”问题：两个状态如果对任意输入串都给出相同的接受/拒绝结果，它们就是不可区分的，可以合并。教材用的分裂法也叫划分细化法，流程固定：
- 初始把状态分成两组：终态组、非终态组。
- 对每一组，逐个检查组内状态：看它们在同一输入符号下分别转移到哪个组。如果两个状态对某个输入符号的转移落入了不同的组，它们就可区分，必须分裂。
- 重复第2步，直到分组不再变化。
这里的关键是“按转移目的组编号”来比较，而不是按具体状态编号比较。习题3-4(1)最小化的过程可以写成下面这张迭代表：
| 轮次 | 分组 | 考察动作 | 结论 |
|---|---|---|---|
| π0 | {1,2}, {3,4} | 状态1读b跳到空集，状态2读b跳到3 | 1和2可区分 |
| π1 | {1}, {2}, {3,4} | 状态3读a跳到1，状态4读a跳到空集 | 3和4可区分 |
| π2 | {1}, {2}, {3}, {4} | 全部分裂 | 终止 |
从表中可以看到，每一轮只比较“当前上一轮的分组”，一旦发现两个状态跳到了不同组，立即把它们拆开。注意π1中{3,4}还保留着，是因为当时还没检查a转移；下一轮检查发现3和4在a上的目标分属{1}和空集，于是继续分裂。不少人在这一步提前停止，导致最小化不彻底。
4.2 习题3-4(4)：不可区分状态的合并
习题3-4(4)是一个能合并状态的例子。确定化重命名后得到4个DFA状态：1 =[A]，2 =[B,C]，3 =[B]，4 =[C]，终态集为{2,4}。
最小化过程：
- π0 = {1,3}, {2,4}
- 检查
{1,3}：状态1读a跳到2，属于{2,4}；状态3读a跳到1，属于{1,3}。看出差别，1和3分裂。 - π1 = {1}, {3}, {2,4}
- 再检查
{2,4}：状态2读a到1，状态4读a到1；状态2读b到4，状态4读b到4。转移目标分别落在同一个组，所以2和4不可区分，保留在同一组。
最后一步的实操作很重要：选择状态2作为{2,4}的代表，删掉状态4，把原来所有指向状态4的边全部改指状态2。转移表中凡是出现4的地方都替换成2，然后把状态4从状态集中移除。
提示：合并时选择哪个状态做代表，原则上任意，但考试和工程实现通常保留编号较小的状态，并且要把终态属性带到代表状态上。2和4原本都是终态，合并后2仍然是终态；如果合并的一组里只有一个终态，代表状态也必须标成终态。
4.3 习题3-8：正规式转DFA的完整状态表
习题3-8要求构造正规式(a|b)*(aa|bb)(a|b)*对应的DFA。正规式直接构造NFA的标准做法是：先为(a|b)*和(aa|bb)分别构造子图，再用ε边串联和并联。构造完成后，用子集构造法确定化，得到7个DFA状态，重命名如下：
| DFA状态 | a | b | 是否终态 |
|---|---|---|---|
| S | A | B | 否 |
| A | C | B | 否 |
| B | A | D | 否 |
| C | C | E | 是 |
| D | F | D | 是 |
| E | F | D | 是 |
| F | C | E | 是 |
初态是S，终态集为{C,D,E,F}。这个状态表值得记住，因为它揭示了正规式的结构：进入终态等价于“已经出现过连续两个相同字符”。验证方法很简单：
aa：S → A → C，C是终态，接受。abba：S → A → B → D → F，D和F都是终态，接受。abab：S → A → B → A → B，全程没进入终态，拒绝，正确。
从这个表也能看出一个实际编码技巧：DFA不需要在每次进入终态后停下来，因为正规式末尾还有(a|b)*，接受后缀任意；只要状态机曾经进入过终态，整个串就属于语言。实现词法分析器时，通常是维护“最近是否进入过接受状态”的标志，而不是在进入终态时立即返回。
5. 第三章应试技巧：方程组法从文法直接解出正规式
5.1 把文法写成方程组
习题3-6是另一种典型考法：给定文法，要求用正规式描述它产生的语言。这类题不需要画状态转换图，用方程组法更快。文法如下：
S → aA A → aA | bB B → bB | cC | c C → cC | c先把每个非终结符对应的产生式写成方程，|写成加号，终结符串保留：
S = aA A = aA + bB B = bB + cC + c C = cC + c方程组的未知数是非终结符，系数是终结符组成的正规式。解这个方程组只需要一条定理：形如X = rX + s的方程，解为X = r*s。这条定理俗称阿登引理，r*是r的闭包，表示可重复零次或多次。
5.2 代入消元计算
解方程要先从没有未知数依赖的最内层开始，这里的C方程只有自身依赖，直接套用阿登引理：
C = cC + c => C = c*c把C = c*c代入B：
B = bB + c*c + c => B = b*(c*c + c)注意这里c*c + c可以化简：c*已经包含零个或多个c，再加一个c等价于c*c，因为c*c里取一次闭包路径就覆盖了c。所以得到：
B = b*c*c继续代入A：
A = aA + b*b*c*c => A = a*b*b*c*c最后代入S：
S = a*a*b*b*c*c这就是文法产生的语言的正规式，与教材答案a*a b*b c*c一致。它读作：至少一个a，后跟至少一个b，再后跟至少一个c。
5.3 几个容易忽略的细节
第一，阿登引理要求方程形如X = rX + s，其中r的解析式不能包含不可终止的环。如果方程写成X = Xr + s，闭包要放在右侧变量的左边，使用时要先通过交换律调整成标准形。第二，代入时不要把闭包的优先级弄混，b*c*c表示b*后接c*再后接c，不能写成b*c* + c之类的形式。第三，化简回归到开始符号S之后，结果里开头的a*a明确表示“至少一个a”，这和语言定义里的n >= 1一一对应，检查时对照题目要求的最小长度即可。
实际做题时更快的路径是：先找到只含单个终结符自环的最内层方程（这里的C = cC + c），解出闭包后向外逐层代入，最后统一化简。这个过程比反复画状态转换图快得多，而且每一步都可以用“最少能接受的串”做反向验证——例如本例的最短串是abc，代入正规式a*a b*b c*c中分别取一个a、一个b、一个c，路径吻合。如果发现最短串对不上，优先检查代入时是否漏掉了终态分支B → c或C → c中的某一个c。
本文还有配套的精品资源，点击获取
