形式语言与自动机作业实战：从DFA到图灵机的核心题型拆解

形式语言与自动机理论，名字听着离工程很远，但在国科大计算机方向，这门0812课程几乎是绕不过去的一块硬骨头。我记得自己当年在选课系统里犹豫了很久，还专门去问过师兄“这门课到底难不难”，师兄很直接：作业能顶住就没事，顶不住就准备再来一次。当时我觉得他夸张，等真正开始做作业才发现，人家讲的是大实话。

这门课研究的是“语言”与“计算模型”之间的关系，核心其实是四个字：形式化建模。你要学会把一段用自然语言描述的“字符串集合”翻译成自动机、文法、图灵机这些严格对象，还要会用泵引理、归约这些工具去证明某些事情做不到。这篇博文就从作业切入，聊聊我做完整个课程作业后的实战体会：题型怎么拆、坑在哪里、工具怎么用，以及怎么把作业经验平移到考试。

1. 课程全貌与作业体系拆解

1.1 这门课到底在讲什么

很多同学第一次看教材目录，会觉得这门课是“四种模型的大杂烩”：有限自动机、下推自动机、图灵机，外加各种文法。但实际学下来你会发现，全课程其实就在讲一件事：语言按“生成能力”和“识别能力”分成了几个层次，每一层都有两套等价的描述方式。比如正则语言这一层，你既可以用DFA（确定有限自动机）去“识别”它，也可以用正则表达式去“生成”它；上下文无关语言这一层，既可以用CFG（上下文无关文法）从生成视角描述，又可以用PDA（下推自动机）从识别视角处理。

这种设计不是巧合。作业里反复出现的“等价转化”题——正则表达到NFA、NFA到DFA、CFG到PDA、任意文法到CNF——本质上就是在让你反复验证这种两层视角的一致性。课程讲授顺序也完全是递进的：从能力最弱的有限自动机开始，逐步放宽限制，一直到图灵机。到了图灵机这一层，你会突然发现前面学的所有模型都能被放到同一张地图里：正则语言是上下文无关语言的真子集，上下文无关语言又是递归可枚举语言的真子集。这个“套娃”结构一旦建立，整门课的骨架就清晰了。

作业在这个阶段的作用，就是逼着你亲手把每一层的“等价性”过一遍。教材里定理的证明写得再漂亮，也不如你自己动手把一个带 ε 转移的NFA转成DFA来得记忆深刻。我在写作业时最明显的感觉是：光看课本觉得自己都懂，一合上书就发现连第一步要怎么设状态都拿不准。所以这门课的作业，与其说是检验，不如说是唯一有效的学习路径。

1.2 作业设计背后的逻辑

我自己做过统计，这份课程的作业题基本可以分成四类。第一类是构造题，给你一个语言描述，让你设计DFA、NFA、正则表达式、CFG或PDA；第二类是证明题，比如用泵引理证明某个语言不是正则的、不是上下文无关的，或者用归约证明某个判定问题不可判定；第三类是转化题，把一个形式对象按要求改为另一个等价形式；第四类是综合题，往往会混合构造和证明，或者要求你比较不同模型的表达能力。

这四类题型在作业里的配比并不是随机的。构造题训练的是从“需求”到“机器”的建模能力，证明题训练的是严谨的量词逻辑和反证思维，转化题考的是对定义细节的精确掌握，而综合题则是把前三种能力捏在一起。到了期末，你会发现考试题几乎全是作业题的变体：换一个语言、换一组符号、换一个限制条件，但解法套路完全一致。所以如果你时间有限，压作业比压课本更划算，这话真不是瞎说。

还有一个容易被忽略的点：作业的书写过程本身就是考试演练。助教批改时会看你的状态转移表是否完整、泵引理证明里的“存在”和“任意”是否写反、CNF转换中有没有漏掉开始符号不能出现在右部这样的细节。这些恰恰是最容易被扣分的地方。养成“把每个符号都写清楚”的习惯，考试时就不会因为跳步而丢分。我自己的体会是，这门课里“写得清楚”本身就是能力的一部分，因为你不能指望读者替你脑补一步转换。

2. 三大核心题型的实操拆解

2.1 自动机构造题：状态转移图是最诚实的表达

先聊最基础的DFA构造题。这类题通常是：给定一个语言，比如“所有由0和1组成、且含有偶数个0和奇数个1的字符串”，让你画出DFA。我见过不少人上来就凭感觉画几个状态，然后测一两个例子觉得没问题就交上去了。这其实是构造题最大的坑，因为DFA是“全函数”，每个状态在字母表上的每个符号都必须有明确的转移，少画一条边都意味着自动机会在某条输入上“卡死”，而这在定义上是不允许的。

我的做法是先问自己一个问题：这个自动机需要“记住”输入串的哪些信息？对于“偶数个0和奇数个1”这个要求，需要记住的信息就是0的个数的奇偶性、1的个数的奇偶性，合起来四种组合，所以状态数基本固定是4个。设状态 q_{ij} 表示“0的个数奇偶性为i、1的个数奇偶性为j”，其中i、j取0或1。初始时读入空串，0的个数和1的个数都是0，也就是偶数，所以初始状态是 q_{00}。读入一个0，0的奇偶性翻转；读入一个1，1的奇偶性翻转。接受状态是所有满足“0为偶数、1为奇数”的状态，也就是 q_{01}。

这里有一个特别容易翻车的细节：空串算不算这个语言的元素。如果题目没有额外说明“字符串非空”，那么空串是包含在“所有由0和1组成”这个范围内的，所以 q_{00} 也有可能是接受状态。很多作业题会故意在这个地方埋雷，比如要求“至少含一个1”，那 q_{00} 就不能作为接受状态，因为空串不含1。你在设计完自动机后，应该立刻检查初始状态是否需要标记为接受状态。我见过不止一次，整个状态转移图画得完全正确，唯独最终漏了在初始状态上加双圈，整道题被扣掉大半分数。

按这个思路，构造DFA的完整流程可以总结成四步：先列出字母表，再确定要记忆的信息，用记忆信息的组合定义状态，最后逐状态逐字符补全转移。补全转移时我习惯先画每个状态的“主干转移”，再回头检查有没有状态在某个符号下没有出口，如果有就补一个指向“死状态”的转移。所谓死状态，就是一旦进入就无法再到达接受状态的状态，它并不是可选的，而是为了满足DFA的“全函数”定义所必需的。作业里经常出现“画出DFA并说明每个状态含义”的要求，状态含义写得好，助教一眼就能看出你的建模思路，即使有小错也会按步骤给分。

2.2 文法设计题：递归才是CFG的灵魂

上下文无关文法的设计题，核心思维和DFA设计完全不同。DFA靠状态记忆信息，而CFG靠递归生成结构。你不会去设计一个“计数器”来保证0和1数量相等，而是会写出 S → 0S1 | ε 这样的产生式，让它一层一层往外包。这种递归视角的转变，是很多同学第一次做CFG作业时最不适应的地方。

我的练习方法是拿到一个语言后先观察它的“结构特征”：是嵌套结构还是并列结构，内层和外层分别有什么约束。比如 L = {a^i b^j c^k | i + j = k}，看到等式就知道这是“c的数量等于a和b的数量之和”，所以文法可以天然地把c当成“外层再包一个a…c或b…c”的结果。于是可以写：

• S → aSc | T
• T → bTc | ε

为什么这样是对的呢？因为每一层往里包，最右边多一个c，左边要么多一个a，要么多一个b，这样整体上a和b的总数始终等于c的总数。这种“数量等式”的约束，在CFG里通常都能用“一个非终结符对应一种配对关系”的方式表达出来。等你多做几道这种题，会发现CFG设计本质上就是把语言拆成若干可以单独递归生成的结构块。

写CFG时还要特别注意一个问题：二义性。作业里有时候会要求“给出文法，并说明其无二义性”，或者“证明该文法是二义性的”。这里我踩过一次坑：写了一个文法能生成正确语言，但同一个句子可以有两棵不同的语法分析树，被助教明确指出来扣了分。后来我每次设计完文法，都会刻意找一两个长度适中的句子，尝试用两种不同方式推导，如果发现能推出两种不同的分析树，就说明文法有隐患。对考试来说，二义性相关题目几乎必考，而且通常和“如何消除二义性”绑定在一起，比如经典的悬空else问题。

另外，CFG作业里还经常要求把文法转换为CNF（Chomsky范式）或GNF（Greibach范式）。这个转换本身是流程化的，但非常考验细心，具体操作我放在后面专门写一节。这里先给一个建议：任何文法设计题，写完后都代入几个正例和反例去验证。正例是“应该能生成的串”，反例是“不应该生成的串”。比如你设计了一个生成a^n b^n的文法，就要检查 aabb 能生成，而 aab 生成不出来。这个验证步骤十分钟就能做完，但能拦住大部分低级错误。

2.3 泵引理证明题：反证法里的量词游戏

泵引理可能是这门课劝退最多人的地方。它的表述本身就带着一堆量词，第一次看很容易懵。我自己的理解方式是把它当成“正面保证”来看：如果一个语言是正则的，那么存在一个泵长度p，任何长度不小于p的句子，都能在靠近开头的地方找到一个“循环块”，把这个循环块重复任意次，得到的句子仍然属于这个语言。证明某个语言不是正则的，就要反着用这个性质说：你不可能找到这个“循环块”，所以语言不是正则的。

以 L = {0^n 1^n | n ≥ 0} 为例。假设L是正则的，那么存在泵长度p。取 w = 0^p 1^p，显然|w| ≥ p且w ∈ L。泵引理保证存在分解 w = xyz，满足 |xy| ≤ p，|y| ≥ 1，且对任意 i ≥ 0，xy^i z ∈ L。因为 |xy| ≤ p，x和y都落在开头那一串0里，所以 y = 0^k 对某个 k ≥ 1 成立。现在取 i = 0，得到 xz = 0^{p-k} 1^p，0的数量比1的数量少k个，不在L中，矛盾。所以L不是正则的。

这个证明看起来很简单，但实际写作业时，最容易犯两个错误。第一个是选取的w没有利用好“|xy| ≤ p”这个约束，比如有人会取 w = 0^p 1^p 时不去分析y一定落在0^p区间内，而是笼统说“无论y怎么取都会导致不平衡”——这在0^n1^n这个例子里碰巧成立，但很多更复杂的题目里不成立，必须严格依赖 |xy| ≤ p 来缩小y的可能位置。第二个错误是把量词顺序写反，比如写成“存在一个y使得…”，让人分不清变量是由谁选定的。泵引理证明的标准句式是：随机给定的p → 我构造w → 引理保证有xyz → 我选择i → 推出矛盾。每一步受谁约束，必须链条一样清晰。

上下文无关语言的泵引理类似，但更繁琐一些，因为要把w拆成五段uvxyz，且约束条件变成 |vxy| ≤ p 和 |vy| ≥ 1。我记得第一次做“证明 L = {a^n b^n c^n | n ≥ 0} 不是上下文无关语言”这道题时，纠结了很久怎么选w才能覆盖所有可能的分解。后来总结出一个经验：尽量选w，使得长度p的“窗口”vxy最多只能覆盖两种字符。典型的选法是 w = a^p b^p c^p，因为 |vxy| ≤ p，窗口不管落在哪里，都不可能同时覆盖a、b、c三种字符，于是当你去“泵”v和y时，总有一种字符的数量不会增加，三种字符数量平衡就会被破坏。这种“窗口选位”的思路，比死记硬背步骤有用得多。

注意：写泵引理证明时，最重要的就是量词顺序。“存在p”“取w”“存在xyz”“取i”——这四句话的顺序严格绑定，谁也不能乱。助教批改时会特别关注你是否真正理解了变量的依赖关系，如果你的证明里混进“对所有分解xyz”这类表述，基本上是致命的。

3. 综合题与转化题的实战现场

3.1 把CFG写成CNF：一步步把“自由”收进笼子

CNF转换是所有转化题里最流程化、也最容易靠细心拿分的一类。我以文法 G 为例：

• S → aXb | ε
• X → aXb | ε

这个文法生成的语言是 a^n b^n（n ≥ 0），看起来很简单，但整个转换过程几乎覆盖了所有需要处理的特殊情况。

第一步，引入新的开始符号 S0，加产生式 S0 → S，目的是让开始符号不出现在任何产生式右部，以后每一步修改只改S的展开，不影响全局。第二步，消除 ε-产生式。这里X → ε和S → ε都是可空产生式。先把所有可空变量找出来：X可空，S也可空，因为S → ε。删除X → ε后，凡是右侧包含X的产生式，都要补上“X不出现”的版本。S → aXb 变成 S → aXb | ab；S → ε删除，但S可空，所以 S0 → S 还要补上 S0 → ε，因为原语言包含空串。

第三步，消除单元产生式。目前有 S0 → S 这一个单元产生式，因为S最终能推导出aXb或ab，所以用 S0 → aXb | ab | ε 替换它。第四步，把终结符也当作非终结符来替换。引入 A → a 和 B → b，然后把所有含a、b的产生式右侧改成AXB和AB，即 S0 → AXB | AB | ε，S → AXB | AB。第五步，处理右侧长度超过2的产生式。AXB长度为3，引入新变量 C → XB，然后改写 S0 → AC | AB | ε，S → AC | AB。X同样有 X → AXB | AB，改写为 X → AC | AB。到这里，所有产生式右侧要么是一个终结符，要么是两个非终结符，CNF就完成了。

整个过程看起来机械，但每一步都有陷阱。比如第四步里很多人会忘记把原来的S产生式也同步替换，导致后面S又冒出终结符a、b。又比如第二步里处理可空变量时，只补了aXb的“X消失”版本，却忘了原产生式本身可能还有别的非终结符也要考虑。我的经验是每做完一步，就把当前所有产生式重新抄一遍，再对照CNF的三个条件逐项检查：开始符号是否只出现在左部、是否存在ε产生式、是否存在单元产生式、每个右部是否合法。这个“抄一遍”看起来浪费时间，但能有效避免边做边懵。

3.2 图灵机设计与归约证明的解题现场

图灵机设计题放在作业里，最大的迷惑性是它看起来像编程。实际上，图灵机作业更强调用“带子操作”来表达算法思路。比如设计一个识别 L = {0^n 1^n 0^n | n ≥ 1} 的图灵机，常见的顶层思路是：先检查串的结构是不是0…01…10…0，然后循环执行“把一个0改成X，把对应位置的一个1改成Y，再把对应位置的一个0改成Z”，直到所有符号都被标记。如果某一步找不到对应符号，就停机拒绝；如果全部匹配完毕，就停机接受。这种描述不需要写出完整的状态表，但要求你能说清楚带子上发生了什么变化、读写头如何往返移动、状态记录了什么信息。作业里如果允许用“高层描述”，一定要把每一步的带子变化描述得足够精确，不能写“继续扫描直到合适位置”就完事，而要说明遇到什么符号如何响应、碰到空白符如何处理。

归约证明是另一个让很多人头疼的题型。以“证明停机问题不可判定”为例：假设 HALT_TM = {⟨M, w⟩ | 图灵机M在输入w上停机} 是可判定的，我们要构造一个判定 A_TM = {⟨M, w⟩ | M接受w} 的算法，而A_TM不可判定是已经在课堂上证明过的结论。归约的关键是构造一个可计算的变换F，把“M是否接受w”这个问题转化成“某个图灵机M'是否在某个输入上停机”。F接受输入⟨M, w⟩，输出一个新的图灵机描述⟨M', w⟩，其中M'的行为是：在输入x上模拟M(w)，注意x本身无关紧要；如果M进入接受状态，M'就停机；如果M进入拒绝状态，M'就进入一个死循环，不停机。

这样，如果M接受w，那么M'在任意x上都会停机；如果M不接受w，那么M'在w上不停机。于是“M接受w”等价于“M'在w上停机”。如果HALT_TM可判定，你就能用它来判断⟨M', w⟩是否停机，从而判断出M是否接受w，这就把A_TM也给判定出来了，矛盾。归约证明里最容易犯方向错误：有人会试图用A_TM的可判定性去证明HALT_TM可判定，方向一反过来证明就废了。判断方向的简单办法是：你的目标是“用B的判定器解A”，所以要把A的实例转换成B的实例，即“A归约到B”，写成 A ≤_m B。如果题目要求证明B不可判定，你应该已知A不可判定，并构造A到B的归约，让B的可判定性反过来推出A可判定，矛盾。

4. 学习工具与复习节奏

4.1 我用过的三个工具

第一个是JFLAP。这是个教学用自动机模拟软件，可以画DFA、NFA、PDA、图灵机，还能模拟运行。写作业时我经常拿它验证自己设计的自动机：把状态转移图输入进去，然后喂十几个测试串，看哪些被接受、哪些被拒绝。最有用的是NFA转DFA功能，它能自动生成子集构造结果，方便你对照检查自己手算的状态集有没有漏。缺点是界面比较老，画图也不太顺手，所以我一般只拿它当“验证器”，不用它画最终提交的图。

第二个是LaTeX + TikZ。TikZ的 automata 库专门用来画自动机状态图。作业要求图文并茂时，用TikZ画图不仅清晰，而且修改起来很方便。我最常用的模板是：

\documentclass{standalone} \usepackage{tikz} \usetikzlibrary{automata, positioning} \begin{document} \begin{tikzpicture}[node distance=2cm] \node[state, initial] (q0) {q0}; \node[state, accepting, right of=q0] (q1) {q1}; \draw (q0) edge[loop above] node {0} (q0); \draw (q0) edge[above] node {1} (q1); \draw (q1) edge[loop above] node {1} (q1); \draw (q1) edge[bend left, below] node {0} (q0); \end{tikzpicture} \end{document}

把这套模板存成文件，每次只需要改动状态名和转移标签。状态之间有多个转移时用 bend left/right 可以让边不重叠。这个面板虽然初学有一点成本，但一份作业画下来基本就熟练了，期末复习时回看也很快。

第三个是Python 的 automata-lib 库。如果某一章作业量特别大，我会写一个小脚本批量验证结果。比如下面这段代码定义了一个识别“偶数个0”的DFA，并检查几个字符串：

from automata.fa.dfa import DFA dfa = DFA( states={"q0", "q1"}, input_symbols={"0", "1"}, transitions={ "q0": {"0": "q1", "1": "q0"}, "q1": {"0": "q0", "1": "q1"}, }, initial_state="q0", final_states={"q0"}, ) for s in ["", "0", "00", "01", "0011"]: print(s, dfa.accepts_input(s))

automata-lib 还支持NFA、PDA和Turing machine的模拟，之前我设计图灵机时也用它跑过几步，确认带子的读写逻辑没有低级错误。工具类的东西不必求多，能覆盖“验证设计”这一个需求就够了。我见过有人花大量时间研究各种可视化插件，最后作业没怎么动笔，这就本末倒置了。

4.2 复习节奏与“错误本”方法

这门课的知识点成体系，但概念密度也高，考前突击基本来不及。我的节奏是：每次作业交完，趁助教还没批改，先把自己做作业时卡壳的地方整理成一个“错误本”。这里的错误不只是算错的题，更重要的是“我为什么会在这卡住”——是状态设计漏了条件，还是泵引理没分析y的位置，还是归约方向搞反了。等到期末复习时，我基本不把教材从头翻一遍，而是直接过错误本，把每个薄弱点对应到课本章节再回看。

另一个对我很有效的办法是找同学讲题。形式语言与自动机里有很多概念，你以为自己懂了，但真让你用一句大白话讲给同学听，往往讲不清楚。每次讲不清楚的地方，就是我理解还有空洞的地方。比如“Myhill-Nerode定理”和DFA最小化之间的关系，我就是靠给同学讲“为什么合并等价状态不会改变识别的语言”才彻底想明白的。几个人每周固定抽一个晚上互相过作业题，讲的人练表达，听的人练挑错，比各自闷头刷题效率高不少。

复习题量不需要特别大，但每道题都要“做到底”。我见过不少同学只看题目的解题思路，觉得“思路对就行了，细节考试时再补”。这门课的考试偏偏喜欢在细节上挖坑，比如要求你在某个转移表里补上缺失的三行，或者给你一个带冗余状态的DFA让你最小化，这种题一步错步步错。平时作业里把每个转移、每个产生式都写完整，考试才能形成肌肉记忆。

5. 常见问题与排查技巧实录

5.1 作业常见问题速查表

下面这张表是根据我和同学讨论时常见的作业问题整理出来的，基本覆盖了作业和考试里最有代表性的扣分点。遇到类似症状直接对照排查，能省下不少时间。

这张表越到复习后期越有用，因为大多数错误不是你不会，而是在高速做题时惯性出错。考前把这张表过一遍，能避免很多“冤枉分”。

5.2 我的三次翻车现场

第一次翻车是在DFA最小化那道作业上。我当时用表格法划分等价状态，划分到最后一步时觉得自己已经把状态分好了，顺手就交了上去。结果助教批注说“初始状态和某个非接受状态被合并了”。我回头一看，原来自己在划分接受状态和非接受状态的第一轮分组时，把初始状态放在了接受状态那一组——其实初始状态不接受任何包含奇数个1的串。从那以后，我每次做最小化或者构造DFA，都会在提交前用JFLAP跑一个“初始状态是否接受空串”的测试，空串这个边界情况真的能抓住很多思维漏洞。

第二次翻车是PDA作业。题目要求设计一个下推自动机识别某个语言，我用的是空栈接受方式，写证明时空栈和终结状态的切换没有写清楚，因为教材里两种接受方式是分节讲的，我在做题时混用了。其实只要选定一种接受方式，语义上就完全够用，但混用会让证明出现逻辑断层。当时我的问题是，栈操作部分用了“栈空即接受”的直觉，可状态定义里又写着“到达终态才接受”，两个标准一交叉，整个自动机到底接受什么串就说不清了。后来我把PDA的七元组完整写出来，明确规定接受条件，这一类问题就再没犯过。

第三次翻车是图灵机设计。我设计了一个看起来完美的高低层算法：标记最左0，找最左1改成Y，再找最左0改成Z，循环。但我在模拟时发现，当所有0和1都匹配完成后，读写头停在磁带中间，下一个动作是继续向右扫描还是退回最左端，我在描述里没有交代，结果就是图灵机不停机。图灵机题最烦人的地方就是“每个状态、每个符号、每个移动方向都必须有定义”，任何悬空的转移都等于死循环。那次之后，我养成了一个习惯：哪怕作业只要求高层描述，我也会至少写出“读写头回退到最左端”这类关键收尾步骤，宁可多写，不可不写。

这三段经历让我最大的收获是：形式语言与自动机这门课，出错往往不是概念不懂，而是定义边界没扣干净。状态转移括号里少写一个字符、证明里少写一个量词、PDA里少交代一个栈操作，都可能导致整个答案被判错。而作业恰恰是你用最小成本去踩这些坑的地方，考试前每一坑都是赚到的。如果你现在正被某道自动机作业卡住，我建议你先别急着硬想，把题目里的语言描述逐字读一遍，问自己三个问题：空串在不在语言里？每个字符都有转移吗？接受条件究竟划到哪一组状态？这三个问题通常能解决一半以上的“我觉得我写对了但结果不对”的疑难杂症。