想象你收到朋友的一本手写旅行手账，第一页写着：“从地铁站出发，如果看到'老城区'路牌，可以向左拐，也可以向右拐；两边的路都能到老城区；对了，还能坐站内的免费摆渡车过去。”整本手账都这样，每个路口都列着三四种走法，你根本没法照着执行。我们把这种“选择困难症”状态的机器叫 NFA（非确定有限自动机）。与之相对，旅行社的行程手册则干脆利落：“从地铁站出发，看到'老城区'路牌，只向左拐。”每个路口只有一条确定路线，这种机器叫 DFA（确定有限自动机）。 而“子集构造算法”，就是一位耐心的行程整理员：它把 NFA 里“所有可能到达的路口”打成一个包，给每个包编一个旅行团号，再把旅行团当作新状态，最终把乱糟糟的手账整理成一本确定性行程手册。这本手册里的每一步都清清楚楚、没有歧义，而且整理员保证：整理前后，你能到达的“盖章景点”完全一样。本文将带你从自动机基础出发，学会计算 ε 闭包、构建状态子集、应对状态爆炸，最后用 Hopcroft 算法给 DFA 减负。

岗位关联

学习子集构造是把正则表达式落地为高效词法分析器的核心技能，也是理解编译器前端、正则引擎与安全检测工具的原理基础。掌握它，你就能看懂从“正则”到“可执行扫描器”的整条流水线。

目录
  1. 可视化演示
  2. 自动机基础
  3. 闭包计算
  4. 子集构建
  5. 算法流程
  6. 状态爆炸
  7. 最小化优化
  8. 工程应用
  9. AI 应用场景
  10. Python 演示
  11. 常见误区
  12. 面试题

可视化演示

子集构造算法将NFA转换为等价的DFA，通过计算状态子集与空闭包消除非确定性。本文详解算法的完整步骤、epsi... 切换模式查看不同维度。

本节配有交互动效（进入视口后自动加载，约 3KB）。

子集构造算法：核心原理 动态展示关键流程与数据流动 交互控件调节参数实时渲染 f(x) = transform(x) 核心概念的可视化呈现

自动机基础

朋友的手账翻到第一页，你会发现它有两个特点：第一，每个路口写了不止一种走法；第二，居然还有虚线箭头标注“免费摆渡车”，不花任何路牌字符就能换乘。这种“选择困难”的机器，就是非确定有限自动机（NFA）。而旅行社那份按图索骥的行程手册，每个路口只写一条路，这种“一条道走到黑”的机器叫确定有限自动机（DFA）。NFA 像个发散思维的策划师，DFA 像个严格执行的执行者。

在计算机科学中，自动机被形式化为一个五元组：状态集合、字母表、转移函数、起始状态和终结状态集合。NFA 与 DFA 的唯一本质区别在于转移函数：NFA 返回一个“岔路集合”，DFA 返回单一路口。但两者之间有一条深刻的定理——它们识别的语言（能被接受的所有字符序列集合）完全相同。这就是子集构造能够成立的理论基石。

所以，整理“选择困难”手账的第一步，是把自动机的四样零件摸清：路口、路牌、岔路规则、入口与盖章点。接下来所有工作——圈团、编号、写新手册——都围着这四个零件打转。

N=(Q,Σ,δ,q0,F)\displaystyle N = (Q, \Sigma, \delta, q_0, F)
这五个零件分别是：路口列表、路牌字符表、岔路规则、出发入口、盖章景点清单。
  1. 状态集合 Q自动机的全部“路口”，有限且非空。
    Q={q0,q1,…,qn}Q = \{ q_0, q_1, \ldots, q_n \}
  2. 字母表 Σ路牌上允许出现的所有字符（如 a、b）。
    Σ={a,b,…}\Sigma = \{ a, b, \ldots \}
  3. 转移函数 δNFA 中“看到某个路牌可以往哪几个路口走”。
    δ:Q×Σ→2Q\delta: Q \times \Sigma \to 2^Q
  4. 起始状态 q0串开始读入之前所在的路口。
    q0∈Qq_0 \in Q
  5. 终结状态集合 F读完整个路牌序列后停在此处则接受。
    F⊆QF \subseteq Q

闭包计算

手账里有一种虚线箭头，旁边标着“免费摆渡车”，坐它不需要消耗任何路牌字符，而且可以连续换乘：从 A 坐上摆渡车到 B，B 又能免费到 C。整理行程时，我们要把所有“免费可达”的路口一次圈进一个集合，这个集合就叫 ε 闭包。ε 是空串记号，意思就是“不读任何字符”。

从数学上看，ε 闭包有两种求法：一是递归定义，自己算一个（零步到达），再加上所有直接 ε 邻居的闭包；二是用迭代算法，从初始状态出发，像在图上做广度优先搜索一样：把状态压入栈，弹出时找它的 ε 邻居，没见过的就标记并继续，直到栈空。两种方式的结论完全一致：ε 闭包是一个“闭合”的状态集，从其中的任何状态出发，沿 ε 箭头游走都不会逃出这个集合。

把这个定义从单状态推广到状态集合 S，就是逐个元素求闭包、再取并集。有了这个“免费可达圈地”的工具，我们就能把 NFA 里那些隐形的静默通道一次性绳之以法。

ε-closure(q)={q}∪⋃r∈δ(q,ε)ε-closure(r)\displaystyle \varepsilon\text{-closure}(q) = \{q\} \cup \bigcup_{r \in \delta(q, \varepsilon)} \varepsilon\text{-closure}(r)
这个公式在说：你的“免费可达范围”等于自己，加上所有一次摆渡可达之地的免费范围。
  1. 零步可达\{q\} 表示“不坐车也算到达自己”。
    {q}⊆ε-closure(q)\{q\} \subseteq \varepsilon\text{-closure}(q)
  2. 收集直接邻居对 δ(q, ε) 中的每个 r，先把它列进候选。
    r∈δ(q,ε)r \in \delta(q, \varepsilon)
  3. 递归展开每个 r 的 ε 闭包再并进来，链条无限延伸。
    ⋃r∈δ(q,ε)ε-closure(r)\bigcup_{r \in \delta(q, \varepsilon)} \varepsilon\text{-closure}(r)
  4. 整体并集所有结果合并成一个大集合，去重后就是闭包。
    ε-closure(q)={q}∪{…}\varepsilon\text{-closure}(q) = \{q\} \cup \{\ldots\}

子集构建

现在整理员开始打包了。他把“当前可能到达的所有路口”装进一个旅行团，给团编号，比如团号 D0。后面无论走到哪一步，整个团一起去、一起回，DFA 里的一个状态就是一个团。这样，“选择困难”就被抹平了：哪怕 NFA 给出五条岔路，DFA 也只需记住“我们现在在这一个团里”。

子集构建的核心操作分两步。第一步，让团里每个成员都沿某个字符（比如 a）走一步，收集所有落点，这叫 move 操作；第二步，对落点集合再做一次 ε 闭包，把免费摆渡也补回来。两步合并，就得到新团。也就是说：DFA 的转移函数，是把 NFA 的“单步转移 + ε 闭包”打包成一个整体来使用。

有了“团”的概念，终态判定也顺理成章：团里只要有一名成员落在盖章景点，整团就算达成目标。这个判定规则在后面最小化时还会用到。

δ′(T,a)=ε-closure(⋃q∈Tδ(q,a))\displaystyle \delta'(T, a) = \varepsilon\text{-closure}\left( \bigcup_{q \in T} \delta(q, a) \right)
从一个旅行团出发，读入一个字符：先各走各的，再统一坐一趟免费摆渡，最后汇合成新旅行团。
  1. 遍历团内成员对当前子集 T 中的每个状态 q 逐一处理。
    q∈Tq \in T
  2. 读取字符走一步用 NFA 的 δ(q, a) 找出 q 读 a 后可到达的所有状态。
    δ(q,a)\delta(q, a)
  3. 合并所有落点对全部成员的结果取并集，得到原始落点集合。
    ⋃q∈Tδ(q,a)\bigcup_{q \in T} \delta(q, a)
  4. 补乘免费摆渡对落点集合整体执行 ε 闭包。
    ε-closure(…)\varepsilon\text{-closure}(\ldots)
  5. 得到新子集结果就是 DFA 中从 T 出发、读入 a 后到达的新状态。
    δ′(T,a)\delta'(T, a)

算法流程

整理手册不是一次性画完所有页面，而是用一个“待办清单”逐页推进。整理员先把起始状态的 ε 闭包写进手册第一页，记为 D0，并把它放进待处理队列。随后循环：从队列里取出一个团，为字母表中每个字符计算转移，生成的新团若没见过就写进手册并加入队列。当队列为空，手册就写完了——没有新团意味着所有“可能的情况”都已覆盖。

算法的正确性基于两个不变式：一是每个 DFA 状态都是 NFA 状态的一个非空子集；二是每个子集都恰好是一次 ε 闭包的结果，因此不会漏掉任何 ε 转移。虽然最坏情况下子集数量可达指数级，但实际操作中，队列机制保证了“用到的才生成、生成过的才处理”，避免了重复劳动。

整理员一遍遍执行“取出—计算—入队”，直到待办清单清空。那一刻，一本确定性的行程手册就诞生了：每一页都只有唯一答案，不再有“选择困难”。

q0′=ε-closure(q0),F′={T∈Q′∣T∩F≠∅}\displaystyle q'_0 = \varepsilon\text{-closure}(q_0), \qquad F' = \{ T \in Q' \mid T \cap F \neq \varnothing \}
初始团是入口的免费可达范围；凡是团里沾了盖章景点的，整团都是“成功之团”。
  1. 初始状态DFA 的起点是 NFA 起点 q0 的 ε 闭包。
    q0′=ε-closure(q0)q'_0 = \varepsilon\text{-closure}(q_0)
  2. 状态空间DFA 的全部状态由所有可达的闭包子集构成。
    Q′={T⊆Q∣T≠∅}Q' = \{ T \subseteq Q \mid T \neq \varnothing \}
  3. 终态判定子集 T 与 NFA 终态集 F 交集非空即为终态。
    T∩F≠∅T \cap F \neq \varnothing
  4. 终止条件工作队列为空时算法结束，手册完成。
    queue=∅\text{queue} = \varnothing

状态爆炸

旅行团编号虽然好用，但这个编号方案有一个隐患：如果有 n 个可选景点，任意组合都可以勉强成一个“团”，编号册最多需要 2 的 n 次方页。NFA 状态越多，DFA 状态越可能爆炸式增长。最经典的反例是“倒数第 k 个字符为 1”的语言：NFA 只需要 k+1 个状态，而任何 DFA 都必须记住最后 k 个字符的全部组合，因此真的需要 2 的 k 次方个状态。

不过，状态爆炸的威胁在工程上可以被缓解：大多数 NFA 产生的子集实际上不可达，真实 DFA 远小于理论最坏值。此外，采用惰性构造（也叫按需构造），只在转移计算真正触达某个子集时才去创建它，能省掉大量永远不会出现的“幽灵团”。在某些极端场景，如果 DFA 实在太大，人们干脆放弃构建，直接对 NFA 做在线模拟——每次读入字符时动态计算子集，用时间换空间。

明白了爆炸的机理，你就不会再被“NFA 很小所以 DFA 一定很小”的错觉欺骗。整理手册时，先别一口气全部印刷，用到哪页印哪页，才是聪明的做法。

∣Q′∣≤2∣Q∣\displaystyle |Q'| \leq 2^{|Q|}
最坏情况下，DFA 的状态数是 NFA 状态数的指数级别，但真实世界里通常远小于这个上限。
  1. 子集个数上限NFA 的 n 个状态，其所有子集共有 2 的 n 次方个。
    ∣2Q∣=2∣Q∣|2^Q| = 2^{|Q|}
  2. DFA 状态的界DFA 每个状态都是 NFA 的一个子集，因此不会超过它。
    ∣Q′∣≤2∣Q∣|Q'| \leq 2^{|Q|}
  3. 可达子集更少从初始子集出发，沿字母表可达的子集通常少得多。
    ∣Qreachable′∣≪2∣Q∣|Q'_{\text{reachable}}| \ll 2^{|Q|}
  4. 时间空间权衡惰性构造优先构建可达子集，必要时退回 NFA 模拟。
    time-space trade-off\text{time-space trade-off}

最小化优化

手册整理完之后，细心的整理员会发现：有些团虽然编号不同，但未来所有路线的走向一模一样——只要读入相同的剩余字符，它们接受或拒绝的结果永远一致。这样的两个团是“等价”的，可以合并成同一个团。合并之后手册更薄，功能却一字不差。

判断两个状态是否等价，最严谨的数学定义是“不可区分性”：对任意长度的后缀串 w，从两个状态出发分别读入 w，要么都被接受，要么都被拒绝。Hopcroft 算法正是基于这个思想：先把所有状态粗分成“终态组”和“非终态组”，然后反复扫描每个分组、每个字母，把组内那些“读同一个字符后落在不同分组”的状态拆开，直到任何分组都无法再细分，也就是达到不动点。这个算法的时间复杂度是 O(n log n)，是 DFA 最小化的经典高效方案。

合并等价团之后，行程手册被精简到“生理极限”——无法再少一个状态。这份最小 DFA 比原始 DFA 更省内存、查表更快，是词法分析器最终想拿到的那一版手册。

q≡r  ⟺  ∀w∈Σ∗,  δ(q,w)∈F⇔δ(r,w)∈F\displaystyle q \equiv r \iff \forall w \in \Sigma^*,\; \delta(q, w) \in F \Leftrightarrow \delta(r, w) \in F
两个路口等价，当且仅当无论后续怎么走，它们要么同时到达盖章景点，要么同时到不了。
  1. 任意后缀串w 遍历所有可能的剩余输入序列。
    w∈Σ∗w \in \Sigma^*
  2. 从 q 出发的结果q 读完 w 后停下的位置是否为终态。
    δ(q,w)∈F\delta(q, w) \in F
  3. 从 r 出发的结果r 读完 w 后停下的位置是否为终态。
    δ(r,w)∈F\delta(r, w) \in F
  4. 等价判定两者对每个 w 的结果都相同才叫等价。
    δ(q,w)∈F⇔δ(r,w)∈F\delta(q, w) \in F \Leftrightarrow \delta(r, w) \in F

工程应用

当整理员终于交付了最小化后的确定性手册，导游就可以照着执行了：每到一个路口，看一眼路牌，翻开手册，走唯一指定的那条路。这个“翻手册”的过程在编译器里就是词法分析——把源代码切分成一个个单词（token）。而整本手册，是由正则表达式一路加工而来的。

工业界的标准流水线是：先用 Thompson 算法把正则表达式编译成 NFA，再用子集构造把 NFA 转成 DFA，最后用 Hopcroft 算法把 DFA 最小化。这条流水线在 Lex/Flex、RE2 等工具中都有完整实现。DFA 的巨大优势是匹配时间与输入长度严格线性——每读一个字符只查一次表，绝无回溯，因此被广泛应用在处理不可信输入的安全引擎中。

从一本乱糟糟的旅行手账，到一本薄而精确的最小行程手册——整条流水线环环相扣。掌握了它，你就掌握了编译器词法分析器的核心引擎。

regex→ThompsonNFA→子集构造DFA→Hopcroft最小DFA\displaystyle \text{regex} \xrightarrow{\text{Thompson}} \text{NFA} \xrightarrow{\text{子集构造}} \text{DFA} \xrightarrow{\text{Hopcroft}} \text{最小DFA}
这是一条“翻译流水线”：正则表达式是人话，NFA 是草稿，DFA 是定稿，最小 DFA 是精装版；每一步都不改变语言。
  1. 正则表达式以简洁的人话描述字符串模式，如“以 abb 结尾”。
    regex\text{regex}
  2. Thompson 构造把正则拆解成带 ε 转移的 NFA 草图。
    regex→NFA\text{regex} \to \text{NFA}
  3. 子集构造用本文学到的打包法把草图变成确定性 DFA。
    NFA→DFA\text{NFA} \to \text{DFA}
  4. Hopcroft 最小化合并等价状态，得到最精简的 DFA。
    DFA→最小 DFA\text{DFA} \to \text{最小 DFA}
  5. 语言守恒每一步都是等价变换，识别的字符串集合不变。
    L(regex)=L(NFA)=L(DFA)L(\text{regex}) = L(\text{NFA}) = L(\text{DFA})

AI 应用场景

词法分析器自动生成（Lex/Flex）

阶段：编译流程中的词法分析阶段

解决的问题：手写词法识别器需要逐字符判断、极易出错且难以维护。AI 工具链中用正则表达式描述单词规则，再自动编译为最小 DFA 扫描器，实现线性时间识别。

具体案例：Flex 工具读取 .l 文件（内有多条正则规则），内部用 Thompson 构造生成 NFA，再用子集构造转成 DFA 并最小化，最终生成 C 语言状态跳转表。编译器前端拿到这张表后，对源代码只做一次线性扫描，就能把关键字、标识符、数字字面量切成 token 流。

正则引擎的线性时间匹配

阶段：文本处理的匹配与验证阶段

解决的问题：传统回溯型正则引擎在处理恶意输入时可能发生灾难性回溯，导致 CPU 被耗尽（ReDoS 攻击）。改用 DFA 后，匹配时间与输入长度严格成正比，从根上消除了回溯风险。

具体案例：Google 的开源正则引擎 RE2 采用“正则 → NFA → DFA”的编译方案，并配合惰性构造避免状态爆炸。它被用在 Go 语言的 regexp 包以及许多日志分析系统中，即使面对数十 MB 的不可信输入也能在毫秒级返回结果。

Python 演示

python71 行
def eps_closure(states, trans):    stack = list(states)    clos = set(states)    while stack:        q = stack.pop()        for r in trans.get((q, ''), []):            if r not in clos:                clos.add(r)                stack.append(r)    return frozenset(clos)  def move(states, ch, trans):    nxt = set()    for q in states:        for r in trans.get((q, ch), []):            nxt.add(r)    return frozenset(nxt)  def subset_construction(trans, alphabet, start, finals):    d0 = eps_closure({start}, trans)    queue = [d0]    seen = {d0}    table = {}    i = 0    while i < len(queue):        cur = queue[i]        i += 1        for ch in alphabet:            nxt = eps_closure(move(cur, ch, trans), trans)            table[(cur, ch)] = nxt            if nxt not in seen:                seen.add(nxt)                queue.append(nxt)    final = {s for s in queue if s & finals}    return d0, queue, table, final  def simulate(dfa_start, table, final, word):    cur = dfa_start    for ch in word:        if (cur, ch) not in table:            return False        cur = table[(cur, ch)]    return cur in final  if __name__ == '__main__':    # (a|b)*abb 的NFA: 状态0~4, 空串key表示epsilon转移    trans = {        (0, ''): [1],        (1, 'a'): [1, 2],        (1, 'b'): [1],        (2, 'b'): [3],        (3, 'b'): [4],    }    alphabet = ['a', 'b']    start = 0    finals = {4}     d0, queue, table, final = subset_construction(trans, alphabet, start, finals)    print('DFA起始子集:', set(d0))    for idx, s in enumerate(queue):        suffix = '  [终态]' if s in final else ''        print('D%d = %s%s' % (idx, sorted(s), suffix))    for (s, ch), t in sorted(table.items(), key=lambda x: (sorted(x[0][0]), x[0][1])):        print("delta(%s, '%s') = %s" % (sorted(s), ch, sorted(t)))     for w in ['abb', 'aabb', 'abbb', 'ab', 'babb', 'bbabb']:        print('%-6s -> %s' % (w, '接受' if simulate(d0, table, final, w) else '拒绝'))
目的：完整演示 NFA 到 DFA 的子集构造，并生成 DFA 转移表用于字符串匹配。
  1. def eps_closure(states, trans):用栈实现 ε 闭包的迭代计算，类似图上的深度优先搜索。
  2. trans.get((q, ''), [])取状态 q 的 ε 邻居；空串键在字典里专门存放 epsilon 转移。
  3. return frozenset(clos)用不可变集合表示 DFA 状态，保证它可以作为字典键。
  4. d0 = eps_closure({start}, trans)初始 DFA 状态是起始状态的 ε 闭包。
  5. queue = [d0]工作列表（待办清单），存放尚未展开转移的子集。
  6. while i < len(queue):边遍历边追加，适合处理“运行中不断有新状态入队”的场景。
  7. nxt = eps_closure(move(cur, ch, trans), trans)核心一行：先走一步，再补闭包。
  8. if nxt not in seen:新团才入队并登记，避免重复处理。
  9. final = {s for s in queue if s & finals}团内有任一 NFA 终态，则整个子集是 DFA 终态。
  10. simulate用生成的 DFA 转移表逐字符模拟匹配，验证转换结果正确。

常见误区

误区“ε 闭包就是沿着 ε 箭头走一步能到的所有状态，不包括自己。”我在手算闭包时经常把起点漏掉。

正解ε 代表“零个字符”，所以零步到达也算到达。闭包的定义是“自身 + 所有 ε 链可达状态”。就像坐免费摆渡车，你站在站台上时，你已经在站台上了。除非显式去掉自身，否则闭包永远包含起点。

为何常见：日常生活中说“可达”通常默认要“走一步以上”，但数学里的闭包运算是包含零步的；初学时容易把图论直觉直接搬过来，忽略了递归定义的基础情形。

误区“NFA 有 5 个状态，转出来的 DFA 也应该是 5 个状态，只是把岔路变成单路而已。”

正解DFA 的一个状态对应的是 NFA 的一个“状态子集”（一个旅行团），而不是单个状态。理论上最坏要 2 的 n 次方个状态。以 (a|b)*abb 为例，5 个状态的 NFA 转换后会得到约 6 个 DFA 状态，数量已经不同；更复杂的例子差距会更大。

为何常见：“等价转换”让人下意识以为结构也一一对应，但 NFA 的“一次多态”本质决定了 DFA 必须用集合来记忆多路线索，状态数自然不是一个量级。

误区“最小化减少了状态数，等于删掉了一些状态，那它能接受的字符串应该变少了吧？”

正解Hopcroft 最小化只合并“完全不可区分”的等价状态——对任意剩余串，两个状态的接受结果都一致。合并是把两个行为一模一样的团并成一个团，绝不改变任何字符串的接受结果。精简的是手册页数，不是路线内容。

为何常见：直觉上“少”意味着“弱”，但这里的“少”去掉的是冗余而非功能；没有理解“等价状态”的严格定义是多选题失分的主要原因。

误区“为了转 DFA，我得把所有 2 的 n 次方个子集全部列出来，再逐个填转移。”

正解标准算法用工作列表按需生成：从初始闭包出发，每次只计算当前团读入各字符后的新团，没出现过的才入队。大量子集根本不可达，永远不会被生成。手动做题时同样只需画“碰得到的团”，不必列全所有组合。

为何常见：教材先讲“子集”再讲“构造”，让人误以为要先把所有子集当成候选状态；实际上惰性构建才是算法的高效关键。

面试题

Q1. NFA 的转移函数 δ(q, a) 的返回值类型是什么？

单选题 · easy

  • A.单个状态
  • B.状态集合← 正确答案
  • C.一个字符
  • D.空状态

答案：B。NFA 允许“选择困难”，同一个输入可以走到多个状态，所以 δ(q, a) 返回状态集合。DFA 的 δ 才返回单个状态。如果把两者记混，后面的子集构造就全都理解错了。

Q2. 子集构造中 DFA 的初始状态是什么？

单选题 · easy

  • A.NFA 的起始状态本身
  • B.所有状态组成的全集
  • C.起始状态的 ε 闭包← 正确答案
  • D.所有终态组成的集合

答案：C。初始 DFA 状态是 NFA 起始状态先做 ε 闭包的结果，因为出发时就能免费蹭摆渡车。只取起始状态本身会漏掉 ε 可达的状态，导致转移表不完整。

Q3. 已知 T = {q1}，δ(q1, a) = {q2}，ε-closure({q2}) = {q2, q3}，则 δ'(T, a) 等于什么？

单选题 · mid

  • A.{q1, q2}
  • B.{q2, q3}← 正确答案
  • C.空集
  • D.{q1, q2, q3}

答案：B。先做 move：从 q1 读 a 到达 {q2}；再对该集合做 ε 闭包，得到 {q2, q3}。注意不要手滑把起始团 T 也并进去，那属于典型误算。

Q4. 设 NFA 终态集 F = {q3}，下列哪个子集是 DFA 的终态？

单选题 · mid

  • A.{q1, q2}
  • B.{q1, q3}← 正确答案
  • C.{q1, q2, q4}
  • D.{q0}

答案：B。终态判定规则是“团里只要有人落在 NFA 终态，整团就是终态”。只有 {q1, q3} 包含 q3，所以它是终态。这个规则用“旅行团里有一个人到盖章点就算成功”来记最稳。

Q5. 一个 n 状态的 NFA 转换成 DFA，最坏情况下 DFA 的状态数是多少？

单选题 · extreme

  • A.n
  • B.n 的平方
  • C.2 的 n 次方← 正确答案
  • D.n 的阶乘

答案：C。DFA 的状态是 NFA 状态的子集，n 个状态的幂集有 2 的 n 次方个元素，这是理论上限。经典反例“倒数第 k 个字符为 1”的语言恰好需要 2 的 k 次方个 DFA 状态。

Q6. Hopcroft 最小化算法的核心策略是什么？

单选题 · hard

  • A.从大到小反复划分等价块直到不动点← 正确答案
  • B.从小到大两两合并状态
  • C.直接删除所有不可达状态
  • D.重新构造一个等价的 NFA

答案：A。Hopcroft 先把状态分为终态组和非终态组，再按“读同一字符落到哪一组”反复细分，直到无法再细分。它是划分法而非合并法，因为合并需要验证两两等价，而划分只需要找出差异。

Q7. 惰性构建 DFA 的核心思想是什么？

单选题 · easy

  • A.预处理全部可能的子集
  • B.只构建从初始闭包实际可达的子集← 正确答案
  • C.每次匹配时重新运行子集构造
  • D.构建完成后不缓存任何转移

答案：B。惰性构建用工作列表按需生成：触达才创建，没见过才入队。大量子集不可达，永远不会被构造，从而避免状态爆炸式地白白占用内存。

Q8. 关于 ε 闭包的正确理解包括哪些？

多选题 · mid

  • A.闭包总包含状态自身← 正确答案
  • B.闭包包含沿 ε 箭头链式可达的所有状态← 正确答案
  • C.闭包不包含状态自身
  • D.闭包的结果仍然是一个状态集合← 正确答案

答案：ABD。ε 闭包 = 自身 + 所有 ε 链可达状态，因此 A、B 正确，C 错误；闭包运算的输出是状态集合，D 正确。闭包是子集构造中反复使用的基础工具。

Q9. 计算 δ'(T, a) 时，需要依次执行哪些操作？

多选题 · mid

  • A.对 T 中每个状态求读 a 后的落点并集← 正确答案
  • B.对并集结果执行 ε 闭包← 正确答案
  • C.将最终结果作为新的 DFA 状态← 正确答案
  • D.直接把 T 的补集当作结果

答案：ABC。标准流程是先 move（所有成员读 a 的落点并集），再闭包（补乘免费摆渡），最后把闭包结果当作 DFA 新状态。补集与子集构造无关，D 是干扰项。

Q10. 关于“正则 → NFA → DFA → 最小 DFA”流水线，下列说法正确的是？

单选题 · hard

  • A.每一步都会改变识别的语言
  • B.Thompson 构造把正则变成 NFA，子集构造把 NFA 变成 DFA，Hopcroft 使 DFA 更精简，且语言全程不变← 正确答案
  • C.最小化后的 DFA 不再能识别原正则的语言
  • D.子集构造会删除 NFA 中的 ε 转移并改变语言

答案：B。整条流水线每一步都是等价变换，语言（能接受的字符串集合）始终不变。最小化合并的是行为完全一致的等价状态，不会影响接受结果。A、C 反对等价性，D 中“删除 ε 转移”属实但“改变语言”错误。