This article does not have a corresponding language version
算法

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

常见概念的说明

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

  • NFA, DFA: 有限自动机(Finite Automata, 下文简称FA)的一种. 具体参见维基百科. 简单的来说,构成一个NFA有5大要素:
  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之后只能抵达一个确定的状态节点.

算法所需操作的定义

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

操作 喵述
ϵ-closure(s) 从状态s出发仅经过ϵ转移能抵达的状态节点集合(包括s自身, 也就是允许0次转移)
ϵ-closure(T) 状态集合T中所有状态的ε-closure的并集, 也就是对输入集合T, 寻找到集合内任意状态节点出发仅经过ϵ转移能抵达的状态节点集合
move(T, a) 计算从集合T出发且通过符号a能直接抵达的状态集合

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

正则表达式 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 exists unmarked T in Dstates:
        Mark T in Dstates # 标记一下我们处理了T,避免重复处理
        # 针对输入的Alphabet中的每一个符号进行遍历
        for all symbols a in Σ:
            # 寻找能从T出发沿着symbol a能抵达的所有状态节点
            # 计算转移, 考虑ϵ转移.
            U = ϵ-closure(move(T, a)) 
            if U is not in Dstates: # 如果计算出的集合U我们没有见过
                Dstates[U] = 'unmarked' # 将U添加到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)

然后,我们来看其核心的函数ϵ-closure是什么样子的:

# 算法的大致思想是,从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

TODO: 算法时间复杂度的分析: 懒, 后面有时间再写.

如果你发现这篇文章有错误的地方,肯请帮忙批评指正!

GouGou, 2025-08-08.

Leave a comment

twikoo