有限自动机DFA与NFA原理

可视化演示

有限自动机是词法分析的理论基石，DFA在每个状态下对同一输入仅有唯一转移，NFA允许非确定性转移与空转移。本文... 切换模式查看不同维度。

自动机模型概述

你刚接手调度中心，第一件事就是给全城地铁建档。档案必须回答五个问题：全城有哪些站台？售票机上卖哪几种票？从每个站台刷卡后能去哪些站？列车从哪一站首发？哪些站台允许乘客出闸？这五条信息合在一起，就是一张能指导实际运营的完整规则书。编译器领域的有限自动机也需要这样一份“官方档案”，它把抽象的识别过程变成一板一眼的数学对象。

这份档案在教科书里叫五元组，五个部件分别对应你刚才问的五个问题。状态集合 Q 是站台名录，字母表 Σ 是车票符号种类，转移函数 δ 是线路指南，初始状态 q₀ 是首发站，终态集合 F 是出闸口开放的站台。只要把这五样东西写清楚，一台自动机就被完整定义了——像设计图纸一样，任何人照着它都能搭出一模一样的地铁网。

自动机“接受”一个输入串，等价于乘客拿着印有一串符号的车票，从首发站出发，每读一个符号就沿着对应线路前进一站，最终停在出闸口开放的站台。反过来，如果走到一半无路可走，或者终点不在终态集合里，这趟行程就被判为“不接受”。有了这份档案，调度员才敢真正指挥列车。不过这时候你发现，老线路图的规则太模糊了——同一个站台居然能通向好几个方向。下一节，我们先看最守规矩的“单轨列车” DFA。

DFA确定性力量

假设你负责的是一条新建的“单轨快线”：每个站台的闸机后面只有一条通道，乘客刷一次卡，闸机上方的指示灯只会亮起一个方向。这条线在设计时就被要求做到绝对确定——同一状态、同一输入，只能有唯一转移。这就是确定性自动机（DFA）的立身之本，也是它名字里"Deterministic"的含义。

形式化地说，DFA 的转移函数是一个普通函数：输入一个站台和一个符号，输出恰好一个站台，绝不会输出“两个选择”。但乘客的票面上印着一长串符号，我们怎么知道整趟旅程的终点呢？这就需要一个能“一次处理一整串”的扩展转移函数。它从初始状态出发，从左到右逐个消耗符号，每一步都调用基础转移函数，最终返回旅程的终点站。

这种“每读一个字符只查一次表”的性质，带来一个巨大的工程红利：线性时间扫描。输入有多长，DFA 就走多少步，绝无回头路。词法分析器最喜欢这种脾气——它可以一遍扫完整个源代码文件，不需要记住任何历史选择点。但确定性也意味着设计者必须把每一条岔路都提前想清楚，稍有疏漏，这张图就会变得臃肿。这时候，你会怀念那张虽然混乱但无比简洁的“蛛网老线路图”。

NFA智能换乘网

老线路图确实混乱：同一个站台，刷一次卡，闸机可能同时打开两个方向；更神奇的是，有些站台之间还藏着“免费换乘通道”，乘客走过去不用消耗任何车票符号。这张图就是非确定有限自动机（NFA）——"Non-deterministic"的意思是，从当前状态读入一个符号，下一步可能落在多个状态中的任意一个，甚至可以不读符号就悄悄换乘。

这种“偷懒”的设定让 NFA 的转移函数变得复杂：它的输出不再是一个状态，而是一个状态的集合。于是转移函数的值域从 Q 变成了 Q 的幂集——所有可能子集构成的集合。理解这一点的关键是：NFA 并不是“真的”随机选择，而是像调度中心同时派出多趟探测列车一样，并行地追踪所有可能的路线。哪条路最终能到达终态，哪条路就代表一种被接受的解释。

你会觉得 NFA 比 DFA 好画得多：描述“以 abb 结尾的字符串”这类模式，NFA 只要寥寥几个状态加几条 ε 边就能画出来，而手工编写 DFA 往往要冥思苦想。可是调度大厅没法直接执行“多种可能”——列车不能真的同时开往两个方向还保证乘客不迷路。于是问题来了：能不能把这张蛛网图，自动改写成一张等价的单轨图？这就是下一节的“客流分析术”。

NFA转DFA算法

地铁调度中心请来一位客流分析专家。专家的思路很巧妙：既然 NFA 在某个时刻可能同时位于多个站台，那我们就不要管单个站台了，直接把“所有可能站台的集合”当成一个虚拟超级站。超级站之间怎么连线？从超级站 S 出发读入符号 a，就把 S 里每一个站台沿 a 能到达的站台全部收集起来，再补上沿途免费换乘通道能到达的站，得到一个新的超级站 S'。这样一张“超级站地图”就是等价 DFA。

这个算法叫子集构造法，其中两个核心操作缺一不可：ε-closure 负责把“免费换乘”走到底，move 负责收集读入一个符号后的一步可达站台。形式化地写，DFA 中从超级站 S 读 a 的转移是这样定义的：

工程实现时有个省力的窍门：只保留从初始超级站出发能实际到达的那些子集，其他永远不会被用到的子集直接丢弃，这就是“可达子集裁剪”。但也要警惕最坏情况：NFA 有 n 个状态时，理论上最多可能产生 2ⁿ 个超级站，这种状态爆炸在写正则表达式时偶尔会咬人一口。不过大多数真实场景里，转换出来的 DFA 规模仍可接受。那张新的单轨图是能跑了，可站台数量还是偏多——下一步，我们要做减法。

DFA状态最小化

新地图画出来了，你盯着它看了半天，发现两个站台的行为模式简直一模一样：从它们出发，读 a 都到同一类地方，读 b 也都到同一类地方，而且它们要么都是终态、要么都不是。既然乘客从这两个站出发的结局永远相同，不如把这两个站台合并成一个“联合大站”，省下运营成本。这类行为无法区分的状态，叫等价状态；把等价状态合并掉，就是 DFA 的状态最小化。

最小化算法用“划分”的手段反复切分状态集合。第一刀先按终态与非终态分成两族——因为终态与非终态在“是否接受”上天生不可混同。接下来每一轮，检查同一族里的两个状态：如果它们对某个符号的转移落到了不同的族，就说明它们行为有差异，必须拆开。不断重复，直到任何两个同族状态对所有符号的后继都在同一族里，划分达到“不动点”。

这个过程做到底，得到的就是该语言同构意义下唯一的最小 DFA——不管最初用哪条路线构造它，最小化之后大家长成一个模样。这份唯一性在工程上价值非凡：它让两个不同人写的词法规则可以公平比较，也让状态表有标准答案。到这儿，你已经能从一张混乱的 NFA 出发，得到一张精炼的单轨图了。但在动手建闸机之前，还差最后一块拼图：正则表达式这门“设计图纸语言”跟自动机到底是什么关系？

正则语言连通

设计师和你开会时，用一套简洁的符号描述出行需求：“所有先随便坐几站、最后三站必须是 abb 的路线”。这种写在纸上的“需求描述语言”就是正则表达式（RE）。你则需要把它翻译成能实际运行的轨道图。好消息是：这两者描述的是同一家族的语言——正则语言。这个结论在理论计算机科学里被称作 Kleene 定理，它把“图纸”和“轨道”之间的鸿沟彻底填平了。

更棒的是，三种表示形式——正则表达式、NFA、DFA——可以任意互转，而且构成一个闭环：正则表达式通过“汤普森构造法”变成 NFA，NFA 用上一节的子集构造变成 DFA，DFA 还能用状态最小化精简，最后最小化后的 DFA 又能反推回更规整的正则表达式。于是“语言”这个概念有了三重身份，任你挑选最顺手的那一种来描述它。

正因这层等价关系，工程上形成一条固定流水线：正则表达式 → NFA → DFA → 最小化。你只需要用直觉写正则，剩下的机械翻译全部交给工具。到这里，理论的地基已经夯实，最后我们回到调度中心的本职工作——词法分析。

词法分析实战

现在，把你的地铁图搬到编译器入口。源代码是一串没有空格分隔的长字符流，乘客是一批批“单词候选”。词法分析器的任务，就是站在闸机口，看着不断滚过的字符，时刻判断：当前读入的这一段，能不能凑成一个合法 token？是关键字 if、标识符 count、数字 42，还是运算符 =？每识别出一个 token，就像放行一位乘客；这个 token 连同它的属性值被送进语法分析器，继续下一段旅程。

实战中最经典的细节是最长匹配原则：当你看到 i、f 两个字符时，它们既可能拼成关键字 if，也可能是标识符 ifx 的开头。闸机必须继续读下去，直到“再多读一个字符就会破坏匹配”为止，才回头兑现最长的那一段。比如输入 ifx，最长匹配结果是标识符 ifx，而不是先输出关键字 if 再输出标识符 x。这个决策用数学表达就是取所有可接受前缀中长度最大的那个。

真实世界中，flex、lex 这类工具就是把你写的正则规则经过“正则→NFA→DFA→最小化”流水线，编译成一张紧凑的跳转表。词法分析器运行时反复查这张表，线性扫描即可完成切分；遇到没有任何规则能匹配的字符，就报告“非法字符”并附上行号列号，精确指出闸机卡在哪一站。从一张地铁图出发，你最终真的建成了编译器的第一道闸机——这就是有限自动机从黑板到工程的全过程。

AI 应用场景

Python 演示

class NFA:    """NFA自动机:用字典表存储转移,支持空转移ε."""     def __init__(self, states, alphabet, trans, start, accepts):        self.states = states                # 状态集合        self.alphabet = alphabet            # 字母表(不含ε)        self.trans = trans                  # 转移表 {(state, sym): {targets}}        self.start = start                  # 初始状态        self.accepts = accepts              # 终态集合     def epsilon_closure(self, states):        """返回从states出发沿空转移能到达的全部状态,包含自身."""        stack = list(states)        closure = set(states)        while stack:            s = stack.pop()            for nxt in self.trans.get((s, ''), ()):                if nxt not in closure:                    closure.add(nxt)                    stack.append(nxt)        return frozenset(closure)     def move(self, states, symbol):        """返回从states出发读入symbol一步可到达的状态."""        result = set()        for s in states:            result.update(self.trans.get((s, symbol), ()))        return result     def to_dfa(self):        """子集构造法:把NFA转换为等价DFA."""        start = self.epsilon_closure({self.start})        unvisited = [start]        dfa_states = [start]        dfa_trans = {}        dfa_accepts = []        while unvisited:            cur = unvisited.pop()            if cur & self.accepts:                dfa_accepts.append(cur)            for symbol in self.alphabet:                nxt = self.epsilon_closure(self.move(cur, symbol))                if not nxt:                    continue                dfa_trans[(cur, symbol)] = nxt                if nxt not in dfa_states:                    dfa_states.append(nxt)                    unvisited.append(nxt)        return DFA(dfa_states, self.alphabet, dfa_trans, start, dfa_accepts)  class DFA:    """确定性自动机:每个状态对每个符号最多一个转移."""     def __init__(self, states, alphabet, trans, start, accepts):        self.states = states        self.alphabet = alphabet        self.trans = trans        self.start = start        self.accepts = set(accepts)     def match(self, word):        """从初始状态出发逐字符读取输入串."""        cur = self.start        for ch in word:            cur = self.trans.get((cur, ch))            if cur is None:                return False        return cur in self.accepts  def main():    # 构造识别正则语言 (a|b)*abb 的NFA    trans = {}    for s in ('q0', 'q1', 'q2', 'q3'):        trans[(s, 'a')] = set()        trans[(s, 'b')] = set()        trans[(s, '')] = set()    trans[('q0', 'a')] = {'q0'}    trans[('q0', 'b')] = {'q0', 'q1'}     # 非确定性:同状态b到两个目标    trans[('q1', 'b')] = {'q2'}    trans[('q2', 'b')] = {'q3'}    nfa = NFA({'q0', 'q1', 'q2', 'q3'}, {'a', 'b'}, trans, 'q0', {'q3'})    dfa = nfa.to_dfa()    tests = ['abb', 'aabb', 'ab', 'babb']    for word in tests:        print(word, '=>', '接受' if dfa.match(word) else '拒绝')  if __name__ == '__main__':    main()

1. trans[(s, '')] = set()为每个状态预置空转移的槽位，保证ε边存在。
2. def epsilon_closure(self, states):ε闭包用栈做深度遍历，把“免费换乘通道”走到头。
3. nxt not in closure避免重复入栈，保证闭包计算的终止。
4. result.update(self.trans.get((s, symbol), ()))move 操作把集合内每个状态的一步目标汇总起来。
5. start = self.epsilon_closure({self.start})DFA 的初始状态要先吞掉所有ε可达状态。
6. cur = unvisited.pop()用栈驱动子集构造的“待展开”超级站列表。
7. if nxt not in dfa_states:只有新的超级站才需要入队展开，这就是可达子集裁剪。
8. trans[('q0', 'b')] = {'q0', 'q1'}一个状态对同一符号有两个目标，这正是 NFA“非确定”的体现。
9. cur = self.trans.get((cur, ch))DFA 每读一个字符只做一次表查询；查不到说明死路，直接拒绝。

常见误区

面试题