状态机设计：从状态转移表到分层状态图

引言

订单状态、协议握手、UI 交互、词法分析——这些看似无关的问题，本质都是有限状态机（FSM）：系统在任何时刻只处于有限个状态之一，由事件驱动转移。状态机的价值不在于"会写 switch"，而在于把散落在代码各处的 if/else 收敛成一张可验证、可可视化、可测试的转移表。本文从四要素讲起，拆解状态转移表与状态图、Mealy/Moore 的输出语义、分层状态机如何化解状态爆炸，再落到三种实现模式与工作流引擎的工程取舍。

前置：正则引擎内部：从 Thompson 构造到回溯与 RE2 线性引擎、DSL 设计实战：内部 DSL、外部 DSL 与解析器构建。形式语言基础见 巴科斯范式（BNF）。

目录

• 1. 状态机四要素：状态、事件、转移、动作
• 2. 状态转移表与状态图
• 3. Mealy 与 Moore：输出依赖谁
• 4. 分层状态机与 Harel 状态图
• 5. 状态爆炸与正交区域
• 6. 实现模式：switch、表驱动与 State 模式
• 7. 状态机与工作流引擎
• 8. 协议与解析器中的状态机
• 9. 测试与可视化
• 10. 速查表与一句话记忆
• 延伸阅读

1. 状态机四要素：状态、事件、转移、动作

任何 FSM 都由四样东西定义：

五个设计原则：① 状态有限且互斥（同一时刻只在一个状态）；② 事件是外部的（状态机被动响应）；③ 转移确定（同状态同事件必到同处，除非含概率/守卫）；④ 动作有边界（副作用集中在转移点）；⑤ 非法转移要显式拒绝（默认拒绝优于默认允许）。

为什么状态机比 if/else 好：if (status == 'paid' && !shipped && ...) 这种条件会随需求膨胀成不可维护的蛛网；状态机把"当前在哪、能去哪"变成一张可枚举的表，非法组合一目了然。

# 反例：条件散落、非法组合靠人脑记
def ship(order):
    if order.status == 'paid' and not order.shipped and not order.canceled:
        order.shipped = True
    # 再加一个状态就得改这里、改那里……

记忆：状态机 = 状态 × 事件 → 新状态 + 动作——把散落的 if/else 收敛成一张可枚举、可验证的表。

2. 状态转移表与状态图

状态转移表是状态机的"真值表"，一行一个 (当前状态, 事件)，单元格是目标状态：

— 表示非法转移（默认拒绝）。这张表本身就是验收标准：任何"表里没有的转移"都该被拒绝。

状态图是同一信息的可视化：圆是状态、箭头是转移、箭头标签是事件。图与表可以互推——先画图理清，再写表落地。

用代码表达表：

TRANSITIONS = {
    ('待支付', '支付成功'): '已支付',
    ('待支付', '取消'):     '已取消',
    ('已支付', '发货'):     '已发货',
    ('已支付', '取消'):     '已退款',
    ('已发货', '确认收货'): '已完成',
}

def next_state(cur, event):
    key = (cur, event)
    if key not in TRANSITIONS:
        raise ValueError(f'非法转移: {cur} --{event}-->')
    return TRANSITIONS[key]

表驱动的好处：新增状态只加行、验证只看表、可视化可自动生成、测试可遍历全表。

记忆：转移表是状态机的真值表——“表里没有的转移一律拒绝”，这张表同时是文档、验收标准和测试用例源。

3. Mealy 与 Moore：输出依赖谁

两种经典模型，差别只在输出何时产生：

Moore 机：输出是状态的函数 output = g(state)。进入"报警"状态就响铃——输出稳定、与输入解耦，但可能需要拆分状态来区分输出。

Mealy 机：输出是状态和输入的函数 output = f(state, input)。同一个"已支付"状态，收到"发货"事件才发短信——状态更少、响应更快，但输出依赖输入路径，验证更复杂。

# Moore：进入状态即输出
def moore(state):
    return {'待支付': '显示付款按钮', '已发货': '显示物流'}[state]

# Mealy：转移时按事件输出
def mealy(state, event):
    if state == '已支付' and event == '发货':
        return '发送发货短信'
    return None

选哪个：默认 Moore（输出语义清晰、状态即输出），当"状态数因输出组合爆炸"时改 Mealy。UI 状态机常用 Moore（状态驱动渲染），协议/通信常用 Mealy（事件驱动响应）。

记忆：Moore 输出看状态（稳、状态多）、Mealy 输出看状态 + 输入（快、状态少）——UI 用 Moore，协议用 Mealy。

4. 分层状态机与 Harel 状态图

平铺状态机的痛点：状态一多，转移数按 状态 × 事件 平方增长，大量转移是"所有状态都响应同一事件"（如全局"取消"）。

分层（Harel）状态图引入超状态：把共享转移提到父状态，子状态自动继承。

[运行中]
  ├── 待机
  ├── 处理中
  └── 暂停
  ↑ 任意子状态收到"关机" → [已关机]（父级转移，子状态共享）

层级带来的三件事：① 转移继承——子状态自动响应父状态的转移；② 默认进入——进入父状态时自动进入某个初始子状态；③ 历史状态——返回父状态时恢复上次的子状态（浅/深历史）。

**历史状态（History）**是分层的杀手锏：一个"媒体播放器"暂停后返回，应回到"暂停前的子状态"（播放中/快进中），而不是重新从"停止"开始。

# 伪代码：带历史的分层状态机
class Player:
    def __init__(self):
        self.parent = 'stopped'
        self.history = None       # 记住上次子状态
    def pause(self):
        self.history = self.sub    # 保存当前子状态
        self.sub = 'paused'
    def resume(self):
        self.sub = self.history or 'playing'   # 恢复历史

SCXML / Statechart 是 Harel 状态图的标准交换格式，XState（JS）等库直接实现它。

记忆：分层把"所有状态都响应的转移"提到父级——超状态继承 + 历史状态恢复，是化解转移爆炸的第一武器。

5. 状态爆炸与正交区域

状态爆炸：多个独立维度的状态相乘。一个"订单"若有 4 个支付状态 × 3 个物流状态 × 2 个退款状态，平铺就是 24 个状态、大量非法组合。

正交区域（Orthogonal Regions）：把独立维度拆成并行子状态机，各自独立演化，用"与"关系组合。

订单 = [支付区] ∧ [物流区] ∧ [售后区]
  支付区：待支付 → 已支付
  物流区：待发货 → 已发货 → 已签收
  售后区：无 → 退款中 → 已退款
  → 三区并行，互不干扰，状态数 4+3+3 = 10 而非 4×3×3 = 36

正交 vs 分层：分层是"或"（任一时刻在某个子状态），正交是"与"（同时在多个区域）。真实系统常两者混用。

守卫条件（Guard）：同一 (状态, 事件) 可因条件走不同目标，转移上挂布尔守卫：

def on_pay(order, amount):
    if amount >= order.total:
        return '已支付'
    elif amount > 0:
        return '部分支付'      # 守卫决定分支
    else:
        raise ValueError('金额非法')

减少状态的四种手段：

1. 正交拆分 —— 独立维度并行，状态数从乘积变求和
2. 分层提父 —— 共享转移上提，去掉重复箭头
3. 守卫分支 —— 同事件多目标，用条件而非拆状态
4. 变量代替状态 —— 连续量（余额、计数）不该是状态，是变量

记忆：状态爆炸的解法是"正交拆维度、分层提父级、守卫分分支、变量别当状态"——独立维度用’与’，互斥维度用’或’。

6. 实现模式：switch、表驱动与 State 模式

三种主流实现，复杂度递增：

① switch / match：最直白，适合小状态机（<10 状态）。

def handle(state, event):
    match (state, event):
        case ('待支付', '支付成功'): return '已支付'
        case ('待支付', '取消'):     return '已取消'
        case _: raise ValueError('非法转移')

优点：无抽象、易读；缺点：状态多了成巨型 switch，动作与转移耦合。

② 表驱动：状态机是一份数据，引擎解释执行。

class FSM:
    def __init__(self, transitions, initial):
        self.t = transitions
        self.state = initial
        self.on_enter = {}
    def fire(self, event, **ctx):
        nxt = self.t.get((self.state, event))
        if nxt is None:
            raise ValueError(f'非法: {self.state} --{event}-->')
        self.state = nxt
        if nxt in self.on_enter:
            self.on_enter[nxt](**ctx)
        return self.state

优点：转移即数据（可配置、可生成、可测试）；缺点：动作回调的组织要设计。

③ State 模式（面向对象）：每个状态一个类，转移是状态对象的方法。

class State:
    def pay(self, order): raise InvalidTransition
class Pending(State):
    def pay(self, order): order.state = Paid()
class Paid(State):
    def ship(self, order): order.state = Shipped()

优点：状态专属行为内聚、易扩展；缺点：类爆炸、跨状态逻辑难共享。

选型：小状态机别上框架（switch 就够）；状态多且要配置化用表驱动；每个状态有大量专属行为用 State 模式。别为 5 个状态引入一个状态机库。

记忆：switch 够小、表驱动够活、State 模式够内聚——按"状态数 × 行为复杂度"选，别为小状态机上重框架。

7. 状态机与工作流引擎

工作流 ≈ 持久化的、带人/服务任务的、可能长跑的状态机。区别在于：

状态机的持久化：状态与转移历史写库，重启后恢复。常见两法：

1. 状态快照 —— 只存当前状态（简单，丢失历史）
2. 事件溯源 —— 存全部事件，重放得状态（可审计，需快照优化）

事件溯源 + 状态机是订单/支付系统的经典组合：每个转移是一个不可变事件，当前状态 = 事件序列的重放。这与 CQRS 天然契合。

版本兼容：长跑工作流升级后，旧实例的状态名可能已改——需要状态迁移或保留旧状态语义。这是工作流引擎比内存状态机难的核心原因。

编排 vs 状态机：Temporal、Cadence 用"工作流代码"隐式表达状态；AWS Step Functions、Camunda 用显式状态图。显式图易可视化、隐式代码易表达复杂逻辑。

记忆：工作流 = 持久化 + 长跑 + 带任务的状态机——内存状态机重启即丢，工作流要处理状态存储、事件溯源与版本兼容。

8. 协议与解析器中的状态机

协议状态机：TCP 连接有 CLOSED/LISTEN/SYN_SENT/ESTABLISHED/… 状态，每个报文是事件——状态机图就是协议规范。

TCP 三次握手（简化）：
  CLOSED --主动打开--> SYN_SENT --收到SYN+ACK--> ESTABLISHED
  LISTEN --收到SYN--> SYN_RCVD --收到ACK--> ESTABLISHED
  任意 --收到RST--> CLOSED

词法分析器就是 DFA：识别标识符、数字、字符串的状态机，正则引擎内部那篇讲的 Thompson 构造/子集构造，产出的就是状态机。

# 极简数字识别 DFA
def is_number(s):
    state = 'start'
    for ch in s:
        if state == 'start' and ch.isdigit():   state = 'int'
        elif state in ('int', 'frac') and ch.isdigit(): pass
        elif state == 'int' and ch == '.':      state = 'frac'
        else: return False
    return state in ('int', 'frac')

状态机与正则的等价：正则表达式、DFA、NFA 描述同一类语言——状态机是它们的"执行形态"。手写解析器用状态机、复杂文法用 BNF/递归下降，两者互补。

状态机在 UI 中的落地：按钮"提交中禁用、成功弹窗、失败可重试"——用状态机建模比一堆布尔标志（isLoading && !isError && …）清晰得多。XState、Zag.js 是 JS 生态的代表。

记忆：协议规范 = 状态机图、词法分析 = DFA、UI 交互 = 状态机——凡"随事件变、状态有限"的问题，状态机都是通用建模语言。

9. 测试与可视化

状态机的可测试性是它最大的红利：转移表就是测试矩阵，可穷举。

三种测试：① 全转移覆盖——遍历转移表每条边，断言目标状态；② 非法转移——断言表外的 (状态, 事件) 都抛错；③ 路径测试——关键序列（下单→支付→发货→收货）端到端。

def test_all_transitions():
    for (cur, event), expected in TRANSITIONS.items():
        assert next_state(cur, event) == expected

def test_illegal_transitions():
    import pytest
    with pytest.raises(ValueError):
        next_state('已完成', '发货')      # 表里没有

属性测试（Property-Based）：随机生成事件序列，断言"状态始终在合法集合内"“不变量永不被破坏”。

# 伪代码：随机事件序列，断言状态合法
for _ in range(10000):
    fsm = FSM(TRANSITIONS, '待支付')
    for event in random_events():
        try:
            fsm.fire(event)
        except ValueError:
            pass
        assert fsm.state in LEGAL_STATES

可视化：从转移表生成 Graphviz DOT，图与代码同源、永不过期。

def to_dot(transitions):
    lines = ['digraph FSM {']
    for (src, event), dst in transitions.items():
        lines.append(f'  "{src}" -> "{dst}" [label="{event}"];')
    lines.append('}')
    return '\n'.join(lines)

状态机库：Python transitions、python-statemachine；JS XState；Java Spring Statemachine。引入库前先确认收益——表驱动 30 行能解决就别上库。

记忆：转移表即测试矩阵——全转移覆盖 + 非法转移断言 + 随机路径属性测试；可视化从表生成 DOT，图与代码同源。

10. 速查表与一句话记忆

全篇速查：

一句话记忆：状态机 = 状态 × 事件 → 新状态 + 动作，它把散落的 if/else 收敛成一张可枚举、可验证、可可视化的真值表，表外的转移一律拒绝；Moore 输出看状态（UI）、Mealy 输出看输入（协议）；状态爆炸用"正交拆独立维度、分层提共享转移、守卫分同事件多目标、连续量别当状态"化解；实现按规模选 switch/表驱动/State 模式，别为 5 个状态上框架；工作流是持久化长跑的状态机，要处理存储、事件溯源与版本兼容；转移表本身就是测试矩阵——全转移覆盖 + 非法转移断言，图与代码同源。

延伸阅读

• 正则引擎内部：从 Thompson 构造到回溯与 RE2 线性引擎
• DSL 设计实战：内部 DSL、外部 DSL 与解析器构建
• 巴科斯范式（BNF）：编程语言语法的元语言描述
• 架构专题 — 状态机在系统设计中的应用
• 分布式系统专题 — 分布式工作流与一致性