非确定性有限自动机：一次保留多个可能世界

DFA 每次只处在一个状态里。读取一个字符，规则表给出唯一的下一个状态。这个约束让 DFA 很容易实现，也让它的执行轨迹很干净：current_state + character -> next_state。

非确定性有限自动机（Nondeterministic Finite Automaton，NFA）放宽了这个约束。同一个状态读取同一个字符时，可以走到多个下一状态；机器还可以在不消耗字符的情况下移动到别的状态。NFA 的实现方式并不神秘：把“当前状态”从单个值改成一个集合，一次保留所有可能路径。

这篇文章用 Python 写一个 NFA，识别两个字符串：ab 和 ba。这个示例足够小，但能完整覆盖 NFA 的两个核心机制：分支和空转移。

非确定性不是随机

“非确定性”容易被误解成机器随机选择一条路。NFA 的更好理解是：同一时刻保留多条候选路径，只要其中一条路径最后进入接受状态，整个输入就被接受。

问题	DFA	NFA
当前状态	一个状态	一组状态
同一输入的下一状态	唯一	可以有多个
是否允许不读字符就移动	不允许	允许
接受条件	当前状态属于接受集合	当前状态集合与接受集合有交集
工程直觉	状态流转表	候选集推进

如果 DFA 的状态轨迹是一条线，NFA 的状态轨迹就是一组同时推进的候选线。实现上不需要真的启动多个线程，也不需要随机试错；集合运算就足够表达这个模型。

模式提炼：单值状态变成候选集

current_state -> current_states

NFA 的关键变化是把单个当前状态提升成状态集合。只要系统需要同时保留多个解释、多个候选、多个分支，就可以先尝试这个模式。

场景	单值模型	候选集模型
DFA / NFA	一个当前状态	多个可能状态
parser	一个解析位置	多个解析分支
规则引擎	一条命中路径	多条候选规则
搜索系统	一个最佳候选	一组候选结果

候选集模型牺牲了一部分空间，换来更直接的分支表达。正则表达式里的 |、?、* 之所以适合先编译成 NFA，就是因为分支天然可以放进集合里。

分支规则和空转移

本文的 NFA 接受 ab 或 ba。起始状态先通过空转移进入两个分支：

start --ε--> try_ab
start --ε--> try_ba

try_ab --a--> seen_a
seen_a --b--> accept

try_ba --b--> seen_b
seen_b --a--> accept

ε 表示不消耗输入字符的移动。代码里会用 None 表示这种空转移。机器刚启动时，虽然显式起点只有 start，但通过空转移可以立刻到达 try_ab 和 try_ba。因此，初始当前状态集合是：

{start, try_ab, try_ba}

输入 ab 时，try_ab 分支会走到 accept；输入 ba 时，try_ba 分支会走到 accept。只要当前状态集合里有 accept，输入就被接受。

规则对象多了一个空字符

FARule 仍然表示一条状态转移。和 DFA 版本相比，唯一变化是 character 可以是 None。

from dataclasses import dataclass


State = str
Character = str | None


@dataclass(frozen=True)
class FARule:
    state: State
    character: Character
    next_state: State

    def applies_to(self, state: State, character: Character) -> bool:
        return self.state == state and self.character == character

    def follow(self) -> State:
        return self.next_state

NFA 的规则表要回答两个问题。第一个问题和 DFA 类似：给定一组当前状态和一个输入字符，可以到达哪些下一状态。第二个问题是 NFA 特有的：不消耗字符时，还能通过空转移扩展出哪些状态。

class NFARulebook:
    def __init__(self, rules: list[FARule]) -> None:
        self.rules = rules

    def next_states(self, states: set[State], character: Character) -> set[State]:
        next_states = set()

        for state in states:
            for rule in self.rules_for(state, character):
                next_states.add(rule.follow())

        return next_states

    def rules_for(self, state: State, character: Character) -> list[FARule]:
        return [rule for rule in self.rules if rule.applies_to(state, character)]

    def follow_free_moves(self, states: set[State]) -> set[State]:
        more_states = self.next_states(states, None)

        if more_states <= states:
            return states

        return self.follow_free_moves(states | more_states)

follow_free_moves 做的是 epsilon closure，也就是空转移闭包。只要还能通过空转移找到新状态，就继续扩展；直到状态集合不再变大为止。

模式提炼：闭包扩展

seed_states -> expand_until_fixed_point(seed_states)

空转移闭包是一种固定点计算。先从一组种子状态出发，不断应用扩展规则；当扩展结果不再增加新成员时，计算停止。

场景	种子	扩展规则	停止条件
NFA 空转移	当前状态集合	ε 转移	没有新状态
依赖分析	直接依赖	依赖的依赖	依赖集合稳定
权限继承	直接角色	父角色 / 组合角色	角色集合稳定
图遍历	起点节点	邻接边	可达集合稳定

听到“从一批对象出发，沿某种关系一直展开到不再变化”时，就可以把它看成闭包扩展。

NFA 的接受条件

NFA 保存的是一组当前状态。每次读取字符前，当前状态集合都要先补齐空转移能到达的状态。

class NFA:
    def __init__(
        self,
        current_states: set[State],
        accept_states: set[State],
        rulebook: NFARulebook,
    ) -> None:
        self._current_states = current_states
        self.accept_states = accept_states
        self.rulebook = rulebook

    @property
    def current_states(self) -> set[State]:
        return self.rulebook.follow_free_moves(self._current_states)

    def accepting(self) -> bool:
        return bool(self.current_states & self.accept_states)

    def read_character(self, character: str) -> None:
        self._current_states = self.rulebook.next_states(
            self.current_states,
            character,
        )

    def read_string(self, text: str) -> None:
        for character in text:
            self.read_character(character)

和 DFA 一样，NFA 会在读取过程中改变当前状态。为了反复测试不同字符串，可以再加一个 NFADesign，每次判断时都创建新的 NFA。

class NFADesign:
    def __init__(
        self,
        start_state: State,
        accept_states: set[State],
        rulebook: NFARulebook,
    ) -> None:
        self.start_state = start_state
        self.accept_states = accept_states
        self.rulebook = rulebook

    def to_nfa(self) -> NFA:
        return NFA({self.start_state}, self.accept_states, self.rulebook)

    def accepts(self, text: str) -> bool:
        nfa = self.to_nfa()
        nfa.read_string(text)
        return nfa.accepting()

完整示例

完整代码如下，可以直接复制运行。

from dataclasses import dataclass


State = str
Character = str | None


@dataclass(frozen=True)
class FARule:
    state: State
    character: Character
    next_state: State

    def applies_to(self, state: State, character: Character) -> bool:
        return self.state == state and self.character == character

    def follow(self) -> State:
        return self.next_state


class NFARulebook:
    def __init__(self, rules: list[FARule]) -> None:
        self.rules = rules

    def next_states(self, states: set[State], character: Character) -> set[State]:
        next_states = set()

        for state in states:
            for rule in self.rules_for(state, character):
                next_states.add(rule.follow())

        return next_states

    def rules_for(self, state: State, character: Character) -> list[FARule]:
        return [rule for rule in self.rules if rule.applies_to(state, character)]

    def follow_free_moves(self, states: set[State]) -> set[State]:
        more_states = self.next_states(states, None)

        if more_states <= states:
            return states

        return self.follow_free_moves(states | more_states)


class NFA:
    def __init__(
        self,
        current_states: set[State],
        accept_states: set[State],
        rulebook: NFARulebook,
    ) -> None:
        self._current_states = current_states
        self.accept_states = accept_states
        self.rulebook = rulebook

    @property
    def current_states(self) -> set[State]:
        return self.rulebook.follow_free_moves(self._current_states)

    def accepting(self) -> bool:
        return bool(self.current_states & self.accept_states)

    def read_character(self, character: str) -> None:
        self._current_states = self.rulebook.next_states(
            self.current_states,
            character,
        )

    def read_string(self, text: str) -> None:
        for character in text:
            self.read_character(character)


class NFADesign:
    def __init__(
        self,
        start_state: State,
        accept_states: set[State],
        rulebook: NFARulebook,
    ) -> None:
        self.start_state = start_state
        self.accept_states = accept_states
        self.rulebook = rulebook

    def to_nfa(self) -> NFA:
        return NFA({self.start_state}, self.accept_states, self.rulebook)

    def accepts(self, text: str) -> bool:
        nfa = self.to_nfa()
        nfa.read_string(text)
        return nfa.accepting()


rulebook = NFARulebook(
    [
        FARule("start", None, "try_ab"),
        FARule("start", None, "try_ba"),
        FARule("try_ab", "a", "seen_a"),
        FARule("seen_a", "b", "accept"),
        FARule("try_ba", "b", "seen_b"),
        FARule("seen_b", "a", "accept"),
    ]
)

design = NFADesign("start", {"accept"}, rulebook)

for sample in ["", "a", "b", "ab", "ba", "aa", "bb", "aba"]:
    print(f"{sample!r:5} -> {design.accepts(sample)}")

运行结果：

''    -> False
'a'   -> False
'b'   -> False
'ab'  -> True
'ba'  -> True
'aa'  -> False
'bb'  -> False
'aba' -> False

ab 和 ba 被接受，其余字符串被拒绝。aba 的前两个字符虽然可以形成 ab，但这台 NFA 没有多余输入的转移规则，读到最后一个 a 后状态集合变空，所以最终拒绝。

看一条状态集合轨迹

对 NFA 来说，轨迹不再是单个状态序列，而是状态集合序列。

def format_states(states: set[State]) -> str:
    return "{" + ", ".join(sorted(states)) + "}"


nfa = design.to_nfa()
print(format_states(nfa.current_states))

for character in "ab":
    nfa.read_character(character)
    print(format_states(nfa.current_states))

运行结果：

{start, try_ab, try_ba}
{seen_a}
{accept}

初始集合里有三个状态，因为 start 可以通过两条空转移同时展开到 try_ab 和 try_ba。读取 a 后，只有 try_ab 分支还能继续；读取 b 后，机器进入 accept。

如果输入是 b，第一步会走到 seen_b；再读 a，同样会进入 accept。NFA 不需要在启动时猜哪条分支正确，它把分支都放进集合里，后续输入会自然淘汰走不通的分支。

Java 程序员的迁移表

Python 写法	Java 对照	作用
set[State]	EnumSet<State>	当前状态集合
`Character = str	None`	Optional<Character> 或专门的 EPSILON 常量
next_states	Set<State> nextStates(Set<State>, Event)	推进候选集
follow_free_moves	固定点循环 / BFS	计算空转移闭包
current_states & accept_states	!Collections.disjoint(current, accept)	判断是否接受
NFADesign	工厂对象 / 不可变配置	避免复用运行态对象

Java 里可以把空转移写成一个专门的事件值，而不是用 null。null 作为转移键容易和“没有规则”混在一起，长期维护不如显式常量清楚。

enum Symbol {
    A, B, EPSILON
}

工程代码通常还会把 followFreeMoves 写成循环，避免递归深度问题。核心思想不变：把直接可达状态加入集合，如果集合变大，就继续扩展。

NFA 和工程里的分支搜索

NFA 的价值不在于运行效率，而在于表达力。很多系统都需要先保留多个候选，再让后续输入继续筛选。

规则引擎里，一个事实可能命中多条规则；消息路由里，一条消息可能匹配多个订阅条件；parser 里，一个 token 序列可能对应多个解析分支；搜索系统里，一个查询可能同时保留多个召回结果。只要后续信息还能淘汰候选，就不要过早压成单个结果。

这种思路和 DFA 的“状态压缩历史”正好互补。DFA 强调把历史压成一个状态，NFA 强调在信息不足时保留多个状态。到了正则表达式编译时，两者会合在一起：正则表达式先自然地编译成 NFA，再在需要时通过子集构造法转成 DFA。

练习

第一，把示例改成接受 ab、ba、aa 三个字符串。提示：从 start 增加一条空转移到新的分支。

第二，给 accept 增加对 a 和 b 的自循环，让机器接受所有以 ab 或 ba 开头的字符串。

第三，改写 follow_free_moves，用 while 循环代替递归。观察状态集合不再变大时怎样退出。

第四，构造一个状态图，让同一个状态读取同一个字符后能到达两个不同状态。打印每一步的状态集合，观察候选路径怎样分裂。

参考资料

• Understanding Computation 官方目录
• Tom Stuart/computationbook 示例代码仓库
• Python 文档：dataclasses
• Python 文档：set 类型
• Java 文档：EnumSet