简介蒋立源《编译原理》第三版第三章习题与答案修改后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 → aa为终结符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保证开头至少一个aA → aA | bB表示a可以继续出现也可以切换到bB → 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状态abS{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状态ab是否终态12空否223否343是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跳到31和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状态ab是否终态SAB否ACB否BAD否CCE是DFD是EFD是FCE是初态是S终态集为{C,D,E,F}。这个状态表值得记住因为它揭示了正规式的结构进入终态等价于“已经出现过连续两个相同字符”。验证方法很简单aaS → A → CC是终态接受。abbaS → A → B → D → FD和F都是终态接受。ababS → 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代入BB bB c*c c B b*(c*c c)注意这里c*c c可以化简c*已经包含零个或多个c再加一个c等价于c*c因为c*c里取一次闭包路径就覆盖了c。所以得到B b*c*c继续代入AA aA b*b*c*c A a*b*b*c*c最后代入SS 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。本文还有配套的精品资源点击获取