3、有限状态机原理：FSM定义、状态、事件、转移、Mealy与Moore类型

3.1 什么是有限状态机？

有限状态机（FSM）说白了就是一个有限个状态的系统。它根据当前状态和输入事件，决定下一步往哪走、输出什么。我在做通信协议解析的时候，发现几乎所有协议——从UART到TCP三次握手——底层都是这么个东西。

一个FSM由以下几个核心要素构成：

• 状态 —— 系统所处的某一稳定局面（比如Idle、Recv、Send）
• 事件 —— 触发状态变化的输入信号或条件
• 转移 —— 状态+事件 → 新状态（+输出）
• 输出 —— 转移过程中或状态中产生的行为

我记得刚入行时写过一个串口解析器，状态图画了十几层，最后发现少考虑了一个边界事件，上线后老丢包。嗯，从那以后我再也不敢轻视FSM的完整性了。

3.2 状态、事件与转移

状态用圆圈或方框表示，事件就是箭头上的标签。一个状态接到一个事件，执行转移，可能产生输出。举个简单的例子——你按下遥控器电源键（事件），电视从“待机”状态转移到“开机”状态，输出一个屏幕亮起。

状态机里的转移规则必须是确定的：同一状态+同一事件 → 唯一的下一个状态。如果出现歧义，那设计就有问题了。

FSM组成要素速览

要素	说明	现实类比
状态	系统当前所处的稳定模式	电梯停在某一层
事件	触发转移的外部输入或条件	乘客按了楼层按钮
转移	从一个状态到另一个状态的路径	电梯关门并上升
输出	转移中或状态内产生的动作	电梯门打开、灯亮

3.3 Mealy与Moore：两种输出机制的差异

这里有个容易搞混的概念——输出到底是依附于转移过程，还是依附于状态本身？这就是Mealy和Moore的分水岭。

• Mealy机：输出发生在转移过程中，依赖当前状态和当前输入。可以更早响应，但组合逻辑复杂。
• Moore机：输出只与当前状态有关，不依赖当前输入。结构简单，但输出会比输入慢一个时钟周期（同步系统中）。

Mealy vs Moore 对比

对比项	Mealy	Moore
输出依赖	当前状态 + 当前输入	仅当前状态
输出时机	转移发生瞬间	状态稳定时
响应速度	较快（输入可直接影响输出）	慢一个时钟（同步设计）
状态数	通常更少（输出隐含在转移中）	可能需要更多状态（输出需单独编码）
典型应用	高速数据总线、协议解析	控制逻辑、时序稳定要求高的系统

3.4 举例：用FSM实现一个简单的“拨号检测”

来段代码看看——假设我们要检测电话拨号时是否拨了“911”。输入是数字序列，状态有：Idle、Got9、Got91、Alarm。

# Moore 风格 — 输出仅由状态决定
state = 'Idle'
while True:
    digit = input()                  # 事件
    if state == 'Idle':
        if digit == '9':
            state = 'Got9'
        else:
            state = 'Idle'
    elif state == 'Got9':
        if digit == '1':
            state = 'Got91'
        elif digit == '9':
            state = 'Got9'
        else:
            state = 'Idle'
    elif state == 'Got91':
        if digit == '1':
            state = 'Alarm'          # 触发警报
        else:
            state = 'Idle'
    # 输出：根据当前状态决定是否报警
    output = True if state == 'Alarm' else False

这是Moore机——输出报警只在Alarm状态成立。如果用Mealy实现，可以在检测到“911”序列的最后一位输入时直接输出报警，无需转到Alarm状态再输出。你想想看，哪种更省事？

3.5 一张图看明白Mealy与Moore的内部结构

下面这张SVG图对比了两种状态机的数据流路径。虚线框表示组合逻辑区域，实线框为寄存器。注意输出信号是从哪里拉出来的：Mealy从组合逻辑输出，Moore从状态寄存器输出。

从图上你一眼就能看出来：Mealy的输出更“急”，Moore的输出更“稳”。实际项目中怎么选？看你是在乎时序还是在乎资源。我个人在低速控制场景（比如按键消抖）用Moore，在高速协议解析（比如SPI从机）用Mealy，还要加输出寄存器打一拍。

3.6 小结：记住三个判断标准

1. 输出是否需要立即响应输入？ — 是则考虑Mealy
2. 输出是否需要干净、无毛刺？ — 是则考虑Moore
3. 状态数是否受限制？ — Mealy通常更省状态

这三条不是铁律，但足够让你在第一次设计时少走弯路。我见过一个同事把Mealy机硬生生画成了状态爆炸图，最后用Moore重构，代码量减半还更稳定。所以别小看这个选择。