上一篇用指称语义把程序翻译成 Python 函数。程序语义这一段到这里已经形成闭环：AST 给出结构，大步语义、小步语义和指称语义分别给出不同角度的含义。接下来进入自动机。问题从“程序怎样执行”换成“机器怎样根据输入移动到下一个状态”。

确定性有限自动机（Deterministic Finite Automaton，DFA）是自动机部分的起点。它没有变量表，没有栈，没有堆，也没有可写纸带；它只记住一个当前状态，然后逐个读取输入字符。每读一个字符，机器就根据一张规则表换到下一个状态。输入读完后，当前状态如果属于接受状态，字符串就被接受；否则被拒绝。

这个模型很小，却足够解释很多工程直觉：订单状态流转、协议解析、词法分析、简单规则匹配，都可以先压成“当前状态 + 输入 -> 下一个状态”的形式。

从业务状态机收缩到形式模型

Java 程序员对状态机并不陌生。订单可以从 CREATED 变成 PAID，再变成 SHIPPED；审批单可以从 DRAFT 变成 SUBMITTED，再变成 APPROVED 或 REJECTED。这些状态机通常带着业务动作、数据库事务、权限检查、通知消息，模型很容易变重。

DFA 把这些东西都拿掉，只保留五个组成部分。

组成部分 含义 本文示例
状态集合 机器可能处在的位置 start、seen_a、accept
输入字母表 允许读取的字符 a、b
转移函数 状态 + 字符 -> 下一个状态 start + a -> seen_a
起始状态 读取输入前的位置 start
接受状态集合 输入读完后代表成功的位置 {accept}

本文的示例任务是识别包含连续子串 ab 的字符串。abb、baba、aaab 会被接受；空字符串、a、b、ba 会被拒绝。这个任务足够小，同时能体现“历史压缩进状态”的关键思想。

DFA 不保存完整输入历史。读到某个位置时，它只知道当前状态。seen_a 表示“刚刚看到过一个可能成为 ab 开头的 a”；accept 表示“已经出现过 ab，后面再读什么都不影响接受结果”。

模式提炼：历史压缩成状态

history -> current_state

状态机的核心价值是压缩历史。系统不需要记住所有发生过的事件，只保留足以决定后续行为的摘要。订单系统不需要每次都重放完整操作日志才能判断能否发货，协议解析器不需要保留所有字节才能判断下一个字节是否合法，DFA 也不需要保留完整字符串才能判断是否已经见过 ab。

场景 原始历史 状态摘要 后续判断
DFA 已读字符 start / seen_a / accept 下一个字符后到哪里
订单流转 历史操作 CREATED / PAID / SHIPPED 当前动作是否合法
协议解析 已读字节 HEADER / BODY / DONE 下一个字节如何解释
词法分析 已读源码片段 IDENTIFIER / NUMBER / SPACE 当前 token 是否结束

听到“行为只取决于当前阶段和下一个事件”时，就应该先想到这个模式。

用规则对象表示转移

第一步是把一条状态转移写成对象。它回答一个问题：当前状态和当前字符是否命中这条规则；如果命中，下一个状态是什么。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
from dataclasses import dataclass


State = str


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

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

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

FARule 是自动机里的最小规则单元。它不关心整个字符串，只关心一次移动。把多条 FARule 放在一起，就得到规则表。

1
2
3
4
5
6
7
8
9
10
class DFARulebook:
    def __init__(self, rules: list[FARule]) -> None:
        self.rules = rules

    def next_state(self, state: State, character: str) -> State:
        for rule in self.rules:
            if rule.applies_to(state, character):
                return rule.follow()

        raise ValueError(f"no rule for state={state!r}, character={character!r}")

真实工程里，规则表通常不会用线性扫描。Java 里更常见的写法是 Map<State, Map<Character, State>>。本文先保留对象列表，是为了让每条规则的含义更清楚。

1
2
3
4
5
6
start  + a -> seen_a
start  + b -> start
seen_a + a -> seen_a
seen_a + b -> accept
accept + a -> accept
accept + b -> accept

对 DFA 来说，确定性有一个硬约束：同一个状态读取同一个字符时，只能有一个下一状态。seen_a + b 不能既去 accept 又回到 start。后面讲 NFA 时，这个约束会被放开。

DFA 只做两件事

DFA 本身只需要保存当前状态、接受状态集合和规则表。读取一个字符时，状态被规则表更新；读取完整字符串时，重复读取每个字符。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class DFA:
    def __init__(
        self,
        current_state: State,
        accept_states: set[State],
        rulebook: DFARulebook,
    ) -> None:
        self.current_state = current_state
        self.accept_states = accept_states
        self.rulebook = rulebook

    def accepting(self) -> bool:
        return self.current_state in self.accept_states

    def read_character(self, character: str) -> None:
        self.current_state = self.rulebook.next_state(
            self.current_state,
            character,
        )

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

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

完整示例可以直接运行。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
from dataclasses import dataclass


State = str


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

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

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


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

    def next_state(self, state: State, character: str) -> State:
        for rule in self.rules:
            if rule.applies_to(state, character):
                return rule.follow()

        raise ValueError(f"no rule for state={state!r}, character={character!r}")


class DFA:
    def __init__(
        self,
        current_state: State,
        accept_states: set[State],
        rulebook: DFARulebook,
    ) -> None:
        self.current_state = current_state
        self.accept_states = accept_states
        self.rulebook = rulebook

    def accepting(self) -> bool:
        return self.current_state in self.accept_states

    def read_character(self, character: str) -> None:
        self.current_state = self.rulebook.next_state(
            self.current_state,
            character,
        )

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

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


contains_ab_rulebook = DFARulebook(
    [
        FARule("start", "a", "seen_a"),
        FARule("start", "b", "start"),
        FARule("seen_a", "a", "seen_a"),
        FARule("seen_a", "b", "accept"),
        FARule("accept", "a", "accept"),
        FARule("accept", "b", "accept"),
    ]
)


def contains_ab(text: str) -> bool:
    dfa = DFA("start", {"accept"}, contains_ab_rulebook)
    return dfa.accepts(text)


for sample in ["", "a", "b", "aa", "ba", "abb", "baba"]:
    print(f"{sample!r:6} -> {contains_ab(sample)}")

运行结果：

1
2
3
4
5
6
7
''     -> False
'a'    -> False
'b'    -> False
'aa'   -> False
'ba'   -> False
'abb'  -> True
'baba' -> True

这里的拒绝不是异常。只要输入字符都在字母表里，DFA 总能读完整个字符串；读完以后不在接受状态，就是拒绝。异常只表示规则表不完整，例如给这台机器输入 c，没有任何规则能处理它。

模式提炼：规则表驱动执行

next = transition_table[current][event]

状态机代码最值得保留的部分不是 if/else 分支，而是转移关系本身。转移关系一旦变成表，系统就能更容易地做可视化、校验、测试覆盖和配置化。

场景 current event next
DFA 当前状态 输入字符 下一个状态
订单流转 订单状态 业务动作 新订单状态
协议解析 解析阶段 当前字节类型 新解析阶段
工作流 节点状态 审批事件 下一节点

当 if/else 开始围绕“当前状态是什么、事件是什么”膨胀时，转移表通常比分支树更稳定。

状态轨迹比结果更有解释力

只看 True 或 False 不够直观。DFA 的执行轨迹可以直接暴露规则怎样生效。

1
2
3
4
5
6
7
8
9
10
11
12
def trace(text: str) -> list[State]:
    dfa = DFA("start", {"accept"}, contains_ab_rulebook)
    states = [dfa.current_state]

    for character in text:
        dfa.read_character(character)
        states.append(dfa.current_state)

    return states


print(" -> ".join(trace("baab")))

运行结果：

1
start -> start -> seen_a -> seen_a -> accept

这条轨迹可以逐步读：

已读字符 当前状态 说明
空 start 还没有看到有用前缀
b start b 不能成为 ab 开头
ba seen_a 末尾的 a 可能成为开头
baa seen_a 新的 a 仍然可能成为开头
baab accept 最后两个字符形成 ab

调试状态机时，轨迹常常比最终状态更重要。业务状态机出现非法流转，词法分析器拆错 token，协议解析器卡在半包位置，都需要先把“输入事件序列 -> 状态轨迹”打出来。

Java 迁移表

同一个模型迁移到 Java 时，代码会更重，但结构完全对应。

Python 写法 Java 对照 作用
State = str enum State 限定状态集合
FARule record Rule(State state, char ch, State next) 一条转移规则
DFARulebook Map<State, Map<Character, State>> 转移表
set[State] EnumSet<State> 接受状态集合
DFA.read_string for (char ch : text.toCharArray()) 消耗输入
DFA.accepting acceptStates.contains(current) 判断是否接受

Java 里的核心代码可以写成表驱动形式。

1
2
3
4
5
6
7
8
9
enum State {
    START, SEEN_A, ACCEPT
}

Map<State, Map<Character, State>> transitions = Map.of(
    State.START, Map.of('a', State.SEEN_A, 'b', State.START),
    State.SEEN_A, Map.of('a', State.SEEN_A, 'b', State.ACCEPT),
    State.ACCEPT, Map.of('a', State.ACCEPT, 'b', State.ACCEPT)
);

如果状态数量少、业务动作多，状态模式也合适：每个状态对象自己决定收到事件后到哪里。DFA 这篇文章更偏向转移表，因为它把“确定性”表达得最直接。

接受状态和拒绝状态

接受状态容易理解，拒绝状态容易被误解。DFA 不一定需要显式的 reject 状态。只要输入读完以后当前状态不在接受集合里，字符串就被拒绝。

在本文示例里，start 和 seen_a 都不是接受状态：

  • 空字符串停在 start，拒绝。
  • a 停在 seen_a，拒绝。
  • ba 也停在 seen_a，拒绝。
  • baba 最终停在 accept，接受。

显式 reject 状态适合另一类规则：一旦出错，后续输入再也无法修复。例如“只接受全是 a 的字符串”，读到第一个 b 后就可以进入 reject，后面读什么都留在 reject。

1
2
3
4
start  + a -> start
start  + b -> reject
reject + a -> reject
reject + b -> reject

本文的 contains_ab 不需要 reject，因为很多暂时失败的前缀仍然可能被后续字符修复。ba 不是接受字符串，但再读一个 b 变成 bab 就接受了。

模式提炼：失败分为可恢复和不可恢复

temporary_failure + more_input -> maybe_success

状态机设计时，要区分“当前还没成功”和“已经不可能成功”。前者只是非接受状态，后者才适合显式 reject 状态。

场景 可恢复失败 不可恢复失败
DFA 匹配 ab 已读 ba，还没有出现 ab 输入了字母表外字符
表单流程 当前字段未填完 必填字段类型非法且不能修正
协议解析 正在等待更多字节 魔数或校验位错误
订单流转 待支付超时前仍可支付 已取消订单不能发货

很多工程 bug 来自把可恢复失败过早做成终态。只要后续事件可能修复局面，状态机就应该保留继续前进的路径。

和正则表达式的关系

contains_ab 用正则表达式可以写成：

1
2
3
import re

bool(re.search("ab", text))

DFA 不是为了替代正则 API。它解释的是正则匹配背后的机器直觉：模式被编译以后，可以变成一套状态和转移规则。每读一个字符，匹配器根据当前状态更新状态；输入读完或匹配成功后，再给出结果。

下一篇会把确定性放开，进入非确定性有限自动机（NFA）。NFA 允许同一个状态在同一个输入上走向多个下一状态，也允许不消耗字符的空转移。正则表达式之所以容易编译成 NFA，正是因为“分支”和“可选路径”在 NFA 里表达得更自然。

练习

第一，把示例改成识别“以 ab 结尾”的字符串。提示：accept 不再能对所有字符自循环。

第二，增加显式 reject 状态，只接受包含 ab 且不包含 bb 的字符串。观察哪些失败是不可恢复的。

第三，把 DFARulebook 改成 dict[tuple[State, str], State]，让查找从线性扫描变成字典查询。

第四，为 trace 增加字符列，输出 start --b--> start --a--> seen_a 这种更适合调试的轨迹。

参考资料