EDIT(2025-12-01): 添加了对ϵ转移的说明。隔了一段时间再看居然有些看不懂ϵ转移了，赶紧复习了下，新增了说明备忘。

EDIT2(2025-12-18): 扩充FA的说明，添加算法优化思路及时间复杂度分析。

EDIT2(2025-12-18): 扩充DFA的说明，添加Dead State.

EDIT3(2025-12-29):修改了算法伪代码, 修正了算法时间复杂度分析(原来的分析是错的!).

常见概念的说明

首先需要对本文用到的概念进行说明. 如果你已经对下述概念很熟悉,可以跳过本节.

• 什么是FA：FA即有限自动机(Finite Automata)，是一种有有限个状态和状态之间转移的有向图。有限自动机也可以成为有限状态机(Finite State Machine). 重点在于有限个状态，以及状态之间的转移。这些转移可以是有条件的，也可以是无条件的；通常一个状态可以绑定一个或多个动作，来表示程序执行到该状态应该执行什么动作。
• NFA(Non-deterministic Finite Automaton, 非确定性有限自动机)和DFA(Deterministic Finite Automaton, 确定性有限自动机)的区别: 先来看NFA的五大构成要素：

1. S: 有限状态集合 S.
2. Σ: 输入符号集合(A set of symbols) : (Input Alphabet).
3. move: 状态转移函数. 这个函数计算对于S中的任意一个状态, 经过符号a之后,可以转移到哪些状态的集合. (包括ϵ转移).
4. s0: 起始状态(Start state/Initial state).
5. F: 终结状态集合 (Accepting states/Final states).

• DFA是NFA的特例:
  1. 状态转移函数move中不包括ϵ转移
  2. 对于一个状态s, 一个输入符号a, move之后只能抵达一个确定的状态节点.
  3. 需要特别注意的是，DFA的状态转移表(move)是针对输入符号集合Σ的任意一个符号c都需要能够找到一条出边。不要问为什么，这是定义。也是DFA的D(Deterministic, adj. 确定的)的由来。

算法所需操作的定义

然后定义几个算法需要用到的操作。

注：这里解释一下什么是ϵ转移。其实这里的"ϵ转移"对应于正则表达式的“|”，也就是“或”的概念（允许无条件转移）。举个栗子：

正则表达式 aa|bb 可以匹配字符串aa或bb，其对应的NFA大致如下图所示

Start ---------ϵ-------> S1 ----a----> S2 -----a-----> End(aa)
         \
          -----ϵ-------> S3 ----b----> S4 -----b-----> End(bb)

其实可以把上面的图看成是：

            / ------ϵ-------> S1 ----a----> S2 -----a-----> End(aa)
Start ----- (OR)       
            \ ------ϵ-------> S3 ----b----> S4 -----b-----> End(bb)

上图的两条标着“ϵ”的线表示S1，S3都可以从Start无条件抵达，而不像是如S1->S2必须要从Input接受字符‘a’才能抵达。 也就是说，我从Start出发，可以先无条件抵达S1，再接受‘aa’(S1->S2)，完整匹配到‘aa’（End(aa)），

或者(OR) 也可以先无条件抵达S3，再接受‘bb’(S3->S4)，完整匹配到‘aa’（End(bb)）。

依照上面的操作定义，先来看看NFA是怎么转换到DFA的. 操作的实现在后面.

算法伪代码

下面是NFA-To-DFA 伪代码：

NFA-To-DFA:

INPUT: NFA’s transition table

OUTPUT: DFA’s trasition table, 标记为Dtrans, 对应的状态集合Dstates.

这里我们用到了函数ϵ-closure(T),这个函数负责寻找从T出发,在不依赖输入(Symbol a)的情况下,所有能无条件抵达的状态节点.

# 我们从s0(Start state)开始处理. 一开始DFA中已知的状态只有s0及ϵ-closure(s0).
def nfa_to_dfa(nfa):
    (S, Σ, move, s0, F) = nfa # nfa 的五大要素
    s0_closure = ϵ-closure(s0)
    # ϵ-closure(s0) 可以理解为从s0出发无条件能抵达的状态.
		# 这里的unmarked是为了方便我们遍历NFA中所有的状态.(遍历一个Mark一个)
    Dstates = {s0_closure: 'unmarked'}
    Dtrans = {}

    while unmarked T in Dstates:
        Mark T # 标记一下我们处理了T,避免重复处理
        # 针对输入的Alphabet中的每一个符号进行遍历
        for all symbols a in Σ:
            # 寻找能从T出发沿着symbol a能抵达的所有状态节点
            # 计算转移, 考虑ϵ转移.
            U = ϵ-closure(move(T, a)) 
            if U is not in Dstates: # 如果计算出的集合U我们没有见过
                Dstates.add(U) # U是Unmarked状态,将其添加到Dstates里,并unmark以便后续遍历.
            Dtrans[T, a] = U # 记录一下从T出发,对于给定的Symbol a能抵达U.
    # 计算一下DFA的Final States (F), 其实就是找一下DFA的状态里面哪些包含了NFA的终结状态.
    F_dfa = {T ∈ Dstates | T ∩ nfa.F ≠ ∅}
    return DFA(Dstates.keys(), Σ, Dtrans, s0_closure, F_dfa)

# 计算ε闭包
# 从T开始,沿着所有的ϵ转移路径进行遍历.
def ε_closure(T):
  	closure = set(T) # 待计算的闭包,包含T中的所有状态.
    stack = list(T) # 使用栈进行深度优先遍历

    while stack:
        t = stack.pop()
        # 遍历所有从t出发的ε转移
        for all u in nfa.move(t, ϵ):
            if u is not in closure:
                closure.add(u)
    return closure

算法优化&算法时间复杂度的分析

算法第16行ϵ-closure(move(T, a)) 调用的算法时间复杂度和的NFA模拟类似，在精心实现之下其所耗时间为O(n+m) (n是NFA节点总数, m是转移总数).

对于从已知正则表达式r转换过来的NFA, 由于其NFA的最大节点数为2|r|, 最大转移数量为4|r|(具体原因可以参考Regex转NFA的McNaughton-Yamada-Thompson Algorithm算法, 具体参见这篇文章: 正则表达式到NFA的转换), 因此在忽略常数的情况下该行的时间复杂度就是O(|r|).

再考虑上这之上的两层循环, 不难得出总体时间复杂度是O(s |r| |Σ|). 其中s是构造出来的DFA中的节点总数.

关于时间复杂度分析的碎碎念

当看到Compilers一书的3.7.5: Efficiency of String-Processing Algorithms的时候,书上介绍说:

Let us consider NFA construct from regex r … For every DFA state constructed, we must construct at most |r| new states, and each one takes at most O(|r|) time.

书上最终给的结果是O(|r|^2^s). 但是我就是特别不理解为什么是这个结果. 直到我看到前面的假设—–

There are at most |r| input symbols.

好嘛,他假设|Σ| <= |r|呗..那最终结果可不就是O(|r|^2^s)嘛. 其实这个书上推论没有考虑到Unicode的情况. 从Unicode Wiki了解到, Unicode能够编码159,801个字符.. 这样就很容易出现 |Σ| >= |r|的情况.

碎碎念: 关于DFA的Dead State

DFA 存在所谓的显式Dead State来处理无效转移，而在NFA中，不发生转移本就意味着输入在该路径上被拒绝，因此不需要显式Dead state。

在传统NFA模拟中，我们可以允许NFA的每一个节点下对于某个输入字符c下不发生任何状态转移（包括e转移）。也就是说，这里NFA拒绝了该输入c。

举个简单的栗子，对于输入Σ = {a, b}， 我们有一个NFA：

  graph LR;
	s(((Start))) --a--> 1((1))
	1((1)) --a--> 2((2))
	2((2)) --a--> 3((3))
	3((3)) --b--> f(((f)))

我们能够经过转移a-a-a-d抵达f(Accepted)节点。由于NFA的性质，假设我们现在正处于3号节点，那么此时输入除了d之外的字符都不会使得NFA发生状态转移。

但是DFA是确定性的有限自动机，DFA下对于每一个节点来说其Alphabet下的每一个输入字符c都必须有一个确定且唯一的出边（其经过转移能抵达的节点必定存在且唯一）。因此DFA不允许存在上述不发生任何状态转移的情况，为了解决这个问题，必须加入一个Dead State，并且对于所有无法匹配的字符来说都指向这个Dead state。

继续上面这个栗子, 在节点3，对于输入b，NFA中我们可以原地踏步—什么转移都不发生，但是DFA内不允许这样的行为。因此我们需要引入一个新的Dead state, 表示匹配无法继续下去了(这里补全了其他节点无法继续匹配的情况）：

  graph LR;
	s(((Start))) --a--> 1((1))
	1((1)) --a--> 2((2))
	2((2)) --a--> 3((3))
	3((3)) --b--> f(((f)))
	3((3)) --a--> Dead(((Dead)))
	2((2)) --b--> Dead(((Dead)))
	1((1)) --b--> Dead(((Dead)))

值得注意的是，如果将NFA转换到DFA，那么节点的每一条出边要么转移到Dead state，要么能够经过一到数次转移至接受状态。

E.O.F Ciallo～(∠・ω< )⌒★