1. 为什么第三章的课后题值得单独拎出来聊
形式语言与自动机这门课，很多人学到第三章会突然感觉“画风变了”。前两章还在跟你聊字母表、字符串、语言的定义，到了第三章，正则表达式、有限自动机、正则文法这几样东西一股脑全冒出来，而且教材往往还会告诉你——它们仨是等价的。这个“等价”两个字，才是第三章课后题真正的核心考点，也是很多人做题时最懵的地方。
我自己当年学这一章的时候，最大的困惑不是单个知识点看不懂，而是不知道题目到底想让我干什么。给你一个正则表达式，让你构造等价的有穷自动机；给你一个自动机，让你写出对应的正则表达式；再给你一个文法，让你判断它是不是正则的。这些题目表面上各玩各的，实际上都在考同一件事：你能不能在三套语言之间自由翻译。
所以这篇内容，我想把第三章课后题里最常见的几类题型拆开，一类一类讲清楚解题思路、操作步骤和容易踩的坑。不管你是正在赶作业，还是准备考试复习，或者只是想把这一章真正搞明白，下面这些内容应该都能帮上忙。我会尽量用大白话把每个步骤说透，让你看完之后拿到题目知道从哪儿下手，而不是对着题目发呆。
2. 第三章课后题的核心考点拆解
2.1 三大等价模型到底在考什么
第三章课后题的所有花样，归根结底都围绕三个东西转：正则表达式、有限自动机（确定型DFA和非确定型NFA）、正则文法（右线性或左线性）。教材花了大篇幅证明它们等价，但课后题不会让你再证一遍等价性，而是让你利用这个等价关系做转换。
为什么这三者等价这件事这么重要？因为在实际问题里，描述同一个模式，用哪种工具方便就用哪种。比如你要写一个词法分析器，正则表达式写起来最简洁；但要让程序去识别，就得转成DFA；而如果你在推导某个语言的生成规则，文法又更自然。课后题就是在训练你这种“换工具”的能力。
常见题型大致可以分成这么几类：
- 正则表达式转NFA（Thompson构造法）
- NFA转DFA（子集构造法）
- DFA转正则表达式（状态消去法或方程组法）
- 正则表达式转正则文法，以及反向转换
- 判断某个语言是否正则，给出证明或反例
- 利用泵引理证明某语言不是正则的
每一类都有固定的套路，但套路里面又有细节差异，下面逐个拆。
2.2 课后题里最容易混淆的几个概念
在动手做题之前，有几个概念必须先分清楚，不然做着做着就乱了。
第一，NFA和DFA的区别不在于“能不能有多个转移”，而在于“确定性”。DFA对每个状态和每个输入符号，最多只有一个转移；NFA可以有多个，也可以有ε转移。很多同学做子集构造法的时候，忘了处理ε闭包，结果构造出来的DFA少状态或者转移不对。
第二，正则表达式的运算符优先级。通常规定是：星号（闭包）最高，然后是连接，最后是并（或）。比如ab*|c应该理解为(a(b*))|c，而不是a(b*|c)。课后题里经常故意不加括号来考你优先级，这个必须记牢。
第三，正则文法的形式限制。右线性文法的产生式形式是 A → aB 或 A → a，左线性是 A → Ba 或 A → a。注意右边最多只有一个非终结符，而且必须在最右边（右线性）或最左边（左线性）。如果产生式右边出现了两个非终结符，那它就不是正则文法，可能是上下文无关甚至更高级别的文法。
把这些分清楚了，后面做题才不会在基本概念上翻车。
3. 正则表达式转NFA：Thompson构造法实操
3.1 构造法的基本规则
Thompson构造法的思路特别朴素：给每个基本的正则表达式片段画一个小自动机，然后用ε转移把它们拼起来。基本规则只有几条：
- 对于单个字符a，构造两个状态，中间一条标a的边。
- 对于连接（如ab），把前一个的接受状态和后一个的起始状态用ε边连起来。
- 对于并（如a|b），新建一个起始状态和一个接受状态，用ε边分别连到两个分支的起止。
- 对于闭包（如a*），新建起止状态，用ε边形成循环和跳过路径。
这套规则的好处是机械、不容易错，缺点是构造出来的NFA状态数偏多，而且ε转移一大堆。但课后题一般不在乎状态数多少，只要结构正确就行。
3.2 一个完整例子：从(a|b)*abb到NFA
拿经典例子(a|b)*abb来走一遍。这个表达式在很多教材里都出现过，因为它既能考闭包、又能考并和连接。
第一步，先处理a|b。新建状态1和2作为起止，1到2有两条边，分别标a和b。实际上更标准的做法是新建一个起始状态和一个接受状态，但为了简化，我们可以直接把1当作起始、2当作接受。
第二步，处理(a|b)*。在刚才的基础上，新建状态0作为新的起始，状态3作为新的接受。0到1有ε边，2到1有ε边（形成循环），0到3有ε边（跳过），2到3也有ε边。
第三步，连接abb。从状态3开始，依次构造a、b、b的链式结构，每个字符两个状态，中间用ε边连接各段。
最终得到的NFA，起始状态是0，接受状态是最后一个b之后的状态。整个构造过程不需要任何灵感，照着规则画就行。
注意：Thompson构造法得到的NFA只有一个接受状态，而且没有从接受状态出发的转移。这个性质在后续转DFA时很有用，可以帮你检查构造是否正确。
3.3 构造过程中的常见错误
我见过最多的错误有三个。一是忘记给并操作新建起止状态，直接把两个分支的边混在一起，导致自动机结构混乱。二是闭包操作时忘了“跳过”的那条ε边，结果星号变成了加号。三是连接操作时没有用ε边把前后两段接起来，而是直接把前一段的接受状态当成后一段的起始状态，这样在形式上虽然有时也能工作，但不符合标准构造法，容易在后续步骤出问题。
还有一个隐蔽的坑：当正则表达式里出现空串ε时，很多人不知道怎么处理。其实很简单，空串对应的自动机就是起始状态同时是接受状态，中间没有边。如果空串参与连接或并，按规则正常拼接即可。
4. NFA转DFA：子集构造法一步步来
4.1 子集构造法的核心思想
子集构造法的本质是：DFA的每个状态对应NFA的一个状态集合。因为NFA在某一步可能同时处于多个状态，DFA就用一个集合来记录所有可能的位置。这样虽然状态数可能爆炸，但至少保证了确定性。
具体操作分三步：
- 计算起始状态的ε闭包，作为DFA的起始状态。
- 对每个DFA状态（即一个NFA状态集合）和每个输入符号，计算转移后的状态集合，再取ε闭包。
- 重复第二步，直到没有新的状态集合出现。
ε闭包的定义是：从某个状态出发，只经过ε边能到达的所有状态的集合（包括自身）。这个计算是子集构造法的基础，必须练到闭着眼睛都能算。
4.2 用表格法组织计算过程
手工做子集构造法时，最容易乱的就是状态集合太多，算着算着就忘了哪个算过哪个没算。我的习惯是画一张表，左边列DFA状态（用集合表示），右边列每个输入符号对应的转移。
拿上一节构造的(a|b)*abb的NFA来举例。假设NFA状态编号是0到10，起始状态0的ε闭包是{0,1,2,4,7}（具体取决于构造细节）。把这个集合记为A，作为DFA的起始状态。
然后对A分别看输入a和b。对a，从A中每个状态出发走a边，到达的状态集合再取ε闭包，得到新集合B。对b同理得到集合C。把B和C加入待处理列表。
接着处理B，再算它对a和b的转移，可能得到新集合，也可能回到已有的A、B、C。如此循环，直到不再产生新集合。
最后，凡是包含NFA接受状态的DFA状态，都标记为DFA的接受状态。
4.3 状态爆炸时怎么办
子集构造法最坏情况下DFA状态数是指数级的，课后题里偶尔会出一些状态数比较多的例子。遇到这种情况，不要慌，按部就班算就行。但如果发现算到一半状态集合越来越多，可以检查一下是不是NFA本身构造得不够精简。
另外，实际做题时不需要把每个集合里的状态都写全，可以用简写，比如用A、B、C代替集合，只要在表格里注明每个字母代表哪个集合就行。这样能省不少书写时间，也不容易抄错。
提示：算完DFA之后，建议回头验证一下。随便挑几个字符串，分别用NFA和DFA跑一遍，看接受结果是否一致。这个验证花不了两分钟，但能帮你发现大部分计算错误。
5. DFA转正则表达式：状态消去法与方程组法
5.1 状态消去法的操作步骤
DFA转正则表达式，课后题里常见的有两种方法：状态消去法和方程组法。状态消去法更直观，适合手工计算；方程组法更系统，适合状态数较多的情况。
状态消去法的思路是：把DFA的状态一个一个“删掉”，每删一个就用正则表达式更新剩下的边，直到只剩起始状态和接受状态，最后那条边上的表达式就是答案。
具体规则是：假设要删除状态q，对于每条进入q的边（标R1）和每条从q出发的边（标R2），如果q有自环（标R3），那么在q的前驱和后继之间新增一条边，标为R1 R3* R2。如果前驱和后继之间本来就有边，用并操作合并。
删状态的顺序可以任意，但经验上先删那些自环少、出入边少的状态，能让表达式简洁一些。
5.2 方程组法的推导过程
方程组法把DFA的每个状态看成一个变量，变量之间的转移关系写成方程组。比如状态q1有到q2的a边和到q3的b边，就写成q1 = a q2 | b q3。如果q1是接受状态，还要加上ε。
然后利用Arden引理求解：如果方程形如X = A X | B，且A不含ε，那么X = A* B。通过逐步消元，最终求出起始状态对应的表达式。
两种方法各有优劣。状态消去法适合状态数少（比如三五个状态）的情况，方程组法适合状态数多但结构规整的情况。课后题里两种都可能出现，建议都练熟。
5.3 表达式化简的实用技巧
不管用哪种方法，最后得到的正则表达式往往比较臃肿，需要化简。常用的化简规则有：
R|R = R（并的幂等律）R|∅ = R（空集是并的单位元）Rε = εR = R（空串是连接的单位元）R∅ = ∅R = ∅（空集是连接的零元）(R*)* = R*（闭包的幂等律）ε|RR* = R*（闭包的展开）
化简的时候不要追求一步到位，先按规则能消的消掉，最后再看整体结构能不能合并。有时候表达式看起来不一样，但实际上是等价的，这种时候不用纠结形式，只要逻辑正确就行。
6. 正则文法与自动机的相互转换
6.1 从正则文法构造NFA
正则文法（右线性）的产生式形如 A → aB 或 A → a。构造NFA的方法很直接：每个非终结符对应一个状态，起始符号对应起始状态。对于产生式 A → aB，画一条从A到B的a边；对于 A → a，画一条从A到一个新接受状态的a边。
如果文法里有 A → ε，那么A对应的状态也要标记为接受状态。如果起始符号能推导出空串，那起始状态就是接受状态。
左线性文法的处理稍微绕一点，需要把产生式反过来看，或者先把文法转换成右线性再构造。课后题里如果出现左线性，一般会要求你先说明它等价于某个右线性文法，然后再构造自动机。
6.2 从DFA构造正则文法
反过来，给一个DFA，构造对应的正则文法也很简单。每个状态对应一个非终结符，起始状态对应起始符号。对于转移 δ(A, a) = B，写产生式 A → aB。对于接受状态F，写产生式 F → ε。
这样得到的文法一定是右线性的。如果DFA有多个接受状态，每个都加一条到ε的产生式即可。
需要注意的是，这样构造出来的文法可能有一些冗余的非终结符或产生式，但课后题一般不做化简要求，结构正确就行。
6.3 转换中的细节陷阱
这里有几个容易出错的地方。第一，DFA的转移是确定的，但文法产生式不要求确定，所以从文法构造NFA时可能出现同一个非终结符有多个相同字符的产生式，这是正常的。第二，如果DFA的某个状态没有对某个输入符号的转移，在文法里就不写对应的产生式，不要凭空补一条。第三，处理ε产生式时要小心，不要给非接受状态加ε产生式，否则会改变语言。
还有一个常见问题是起始符号的处理。如果起始符号出现在某个产生式的右边，那它就不是起始符号了，需要引入新的起始符号。这个细节在课后题里经常被忽略，但严格来说必须处理。
7. 泵引理证明题：怎么下手才不慌
7.1 泵引理的标准证明框架
泵引理是用来证明某个语言不是正则的。课后题里这类题往往让很多人头疼，因为不像构造题那样有固定步骤。但其实泵引理的证明也有套路，按框架走就行。
标准框架是：
- 假设语言L是正则的，那么存在泵长度p。
- 从L中选一个长度不小于p的字符串s，通常选得巧妙一点，让后面的矛盾容易导出。
- 把s拆成xyz，满足 |xy| ≤ p 且 |y| ≥ 1。
- 证明对于某个i，xy^i z不在L中，从而矛盾。
- 得出结论L不是正则的。
关键在于第二步选字符串和第四步找i。选字符串时要让y的可能形式有限且可控，找i时通常选i=0或i=2就能出矛盾。
7.2 选字符串和拆分的技巧
选字符串的核心原则是：让y落在你希望它落的地方。因为 |xy| ≤ p，所以y一定在前p个字符里。如果你选的字符串前p个字符有某种规律，就能限制y的可能形式。
比如要证明 {a^n b^n | n ≥ 0} 不是正则的，选 s = a^p b^p。因为 |xy| ≤ p，所以y只能由a组成。那么xy^0z = a^(p-|y|) b^p，a和b的数量不相等，矛盾。
再比如要证明 {ww | w ∈ {a,b}*} 不是正则的，选 s = a^p b a^p b。y落在前p个字符里，只能是a的重复。泵之后a的数量变了，但b的位置没变，导致无法形成ww的形式。
7.3 常见错误与避坑指南
最常见的错误是选了一个太“灵活”的字符串，导致y的可能形式太多，没法一一排除。比如选s = a^p b^p c^p，虽然看起来对称，但y可能落在a段、b段或c段，需要分情况讨论，增加了工作量。更好的选择是让前p个字符只有一种字符，这样y的形式就唯一了。
另一个错误是忘了验证 |xy| ≤ p 和 |y| ≥ 1 这两个条件。这两个条件是泵引理给的，必须满足，否则拆分不合法。
还有一个隐蔽的坑：泵引理是必要条件，不是充分条件。也就是说，一个语言满足泵引理，不一定是正则的。所以泵引理只能用来证明“不是正则”，不能用来证明“是正则”。课后题里如果让你判断一个语言是否正则，用泵引理只能给出否定答案，肯定答案需要构造自动机或正则表达式。
8. 课后题实战：几道典型题目的完整解答
8.1 题目一：正则表达式转DFA
题目：构造与正则表达式(a|b)*a(a|b)等价的DFA。
解题思路：先按Thompson构造法得到NFA，再用子集构造法转DFA。这个表达式表示“倒数第二个字符是a”的所有字符串。
NFA的构造这里不展开画图，重点说子集构造的过程。起始状态的ε闭包包含表达式的起始部分。经过计算，最终得到的DFA有四个状态，分别对应“还没看到a”、“刚看到a”、“看到a后又看到一个字符”、“看到a后又看到两个字符”这几种情况。接受状态是最后一种。
这道题的关键在于理解表达式的含义，这样在验证DFA时能快速判断对错。比如字符串“aba”应该被接受，因为倒数第二个字符是a；“abb”不应该被接受，因为倒数第二个字符是b。
8.2 题目二：DFA转正则表达式
题目：给定一个DFA，状态转移如下表，求等价的正则表达式。
| 状态 | a | b |
|---|---|---|
| →q0 | q1 | q0 |
| q1 | q1 | q2 |
| *q2 | q1 | q0 |
用状态消去法，先删q1。q1有自环a，进入q1的边有q0的a和q2的a，从q1出发的边有到q2的b。所以新增q0到q2的边标aab，q2到q2的边标aab。然后删q2，最后得到表达式。
具体计算过程这里省略中间步骤，最终结果是b* a a* (b | a a*)*之类的形式。不同消去顺序可能得到不同但等价的表达式，这是正常的。
8.3 题目三：泵引理证明
题目：证明 L = {a^n b^n c^n | n ≥ 0} 不是正则的。
证明：假设L是正则的，泵长度为p。选 s = a^p b^p c^p。因为 |xy| ≤ p，所以y只由a组成。取 i = 0，则 xy^0z = a^(p-|y|) b^p c^p。此时a的数量小于b和c的数量，不满足a^n b^n c^n的形式，所以不在L中。矛盾。因此L不是正则的。
这道题是泵引理的经典应用，选字符串和取i都很直接。关键是理解为什么y只能由a组成——因为前p个字符全是a。
9. 复习第三章的几点个人建议
第三章的内容看起来杂，但其实主线很清晰：三套模型、两个转换方向、一个泵引理。复习的时候不要孤立地背每个知识点，而是画一张关系图，把正则表达式、NFA、DFA、正则文法这四个东西用箭头连起来，每个箭头代表一种转换方法。这样遇到题目时，先判断起点和终点是什么，然后沿着箭头走就行。
做题的时候，我建议养成两个习惯。一是每构造完一个自动机，随手验证两三个字符串，确认接受结果符合预期。这个习惯能帮你抓住大部分低级错误。二是写正则表达式时，不确定优先级就加括号，虽然看起来啰嗦，但能避免歧义。
还有一点，课后题里有些题目是“证明或反驳”，这种题往往没有标准答案的固定形式，需要你自己组织论证。遇到这种题，先判断命题的真假，真的就构造自动机或文法，假的就用泵引理或反例。不要一上来就试图证明，先花一分钟判断真假，能省很多时间。
最后说一个我自己的教训。当年做第三章作业时，我总觉得子集构造法太繁琐，想偷懒跳过ε闭包的计算，结果构造出来的DFA总是差几个状态。后来老老实实把ε闭包算清楚，正确率立刻上去了。这一章的内容，繁琐的地方恰恰是考点所在，偷懒省下的时间，最后都会在检查时加倍还回去。
