3. FSM的表示方法：状态转移图、状态转移表、状态矩阵、伪代码与数学形式化描述

有限状态机（FSM）的设计本质上是将系统的行为逻辑抽象为“状态—事件—动作”的三元关系。同一个FSM可以用多种不同的形式化语言来描述，每种表示方法在可读性、精确性、可验证性和工程可实施性上各有侧重。状态转移图直观、状态转移表严谨、状态矩阵适合算法处理、伪代码贴近实现、数学形式化描述则服务于模型检验与形式化验证。在实际工程中，设计者往往需要根据设计阶段（需求分析、详细设计、编码实现、验证测试）灵活切换多种表示方法，并保持它们之间的一致性。本章将系统讲解五种主流表示方法的原理、构建流程、适用场景及相互转换关系，并通过一个电梯控制器案例贯穿始终，帮助读者建立多视角建模能力。

3.1 状态转移图：直观建模与沟通的基石

3.1.1 核心原理与图形元素

状态转移图（State Transition Diagram, STD）是FSM最直观的图形化表示方法，源自Mealy和Moore机理论。其基本图形元素包括：状态节点（圆角矩形或圆形，表示系统在某一时刻所处的稳定状态）、转移箭头（有向弧线，表示在特定事件触发下从一个状态迁移到另一个状态）、事件标签（标注在箭头上的触发条件，格式为“事件[守卫条件]/动作”）、初始状态标记（实心圆点+箭头指向初始状态）以及终止状态（双圈圆，可选）。在Moore机中，动作标注在状态节点内部；在Mealy机中，动作标注在转移箭头上。实际工程中，混合标注方式也常见——状态内标注进入动作（entry action），箭头上标注转移动作（transition action）。

3.1.2 绘制方法与操作流程

绘制状态转移图应遵循以下步骤：第一步，列出所有可能的系统状态，去除重复和等价状态；第二步，确定触发状态转移的事件集合（包括外部事件、内部定时器事件、信号量事件等）；第三步，为每个状态分析所有可能的事件响应，确定目标状态和输出动作；第四步，绘制图形并检查完备性——每个状态在任意事件下都必须有明确的转移路径（包括自环转移）；第五步，进行可达性检查，确保所有状态从初始状态均可到达。在绘制工具选择上，UML状态图、Stateflow、Graphviz、draw.io 均可支持，但需注意不同工具对“转移优先级”和“守卫条件”的语义支持存在差异。

3.1.3 常见误区与复盘

• 遗漏自环转移：在状态“开门”中，若收到重复的开门按钮事件，应保持开门状态并重置超时定时器，若未绘制自环转移，实现时可能产生未定义行为。
• 事件与动作混淆：事件是触发条件，动作是响应结果。初学者常将“超时”事件直接写成“关门”动作，导致语义混乱。
• 未标注守卫条件：同一事件在不同守卫条件下可能导向不同目标状态，如“呼叫”事件在“当前楼层=目标楼层”时不应触发转移。

3.2 状态转移表：完备性与可验证性的保障

3.2.1 核心原理与表格结构

状态转移表（State Transition Table, STT）以二维表格形式描述FSM的行为。标准结构为：行对应当前状态，列对应事件（或输入符号），单元格内容为目标状态和输出动作。对于Mealy机，单元格格式为“目标状态/输出动作”；对于Moore机，输出动作单独列在状态列中。状态转移表的最大优势在于完备性检查——表格中不允许存在空白单元格，每个状态对每个事件都必须有明确的响应，这迫使设计者系统性地思考所有可能情况。

3.2.2 构建流程与检查方法

构建状态转移表时，建议采用以下流程：第一步，从状态转移图中提取所有状态和事件，建立表格框架；第二步，逐行逐列填充目标状态和动作，对于不可能发生的事件组合，明确标注“不可能”或“忽略”并说明原因；第三步，进行一致性检查——对比状态转移图与表格，确保两者描述完全一致；第四步，进行可达性分析——从初始状态出发，通过表格追踪所有可达状态，标记不可达状态（通常是设计冗余或错误）。

3.3 状态矩阵：面向算法与自动化的紧凑表示

3.3.1 核心原理与矩阵定义

状态矩阵（State Matrix）是状态转移表的数学化压缩形式，将状态和事件分别映射为矩阵的行索引和列索引。定义状态集合 S = {s₁, s₂, ..., sₙ}，事件集合 E = {e₁, e₂, ..., eₘ}，则状态转移矩阵 T 为 n×m 矩阵，其中元素 T[i][j] 表示在状态 sᵢ 下发生事件 eⱼ 时的目标状态索引。若同时需要表示输出动作，可定义输出矩阵 O，O[i][j] 存储对应的动作编码。状态矩阵的优势在于：存储紧凑（n×m 个元素即可完整描述）、适合程序化处理（可直接作为查表法状态机的实现基础）、便于数学运算（如矩阵乘法可用于计算多步转移关系）。

3.3.2 构建方法与工程应用

构建状态矩阵时，首先为每个状态分配唯一整数编号（0~n-1），为每个事件分配唯一整数编号（0~m-1），然后填充矩阵元素。在嵌入式系统中，状态矩阵常以二维数组形式存储在ROM中，配合事件驱动调度器实现高效的状态机执行引擎。例如，电梯控制器的状态矩阵可定义为 uint8_t next_state[6][6]，其中行索引对应当前状态编号，列索引对应事件编号，数组元素为目标状态编号。这种实现方式的时间复杂度为 O(1)，且易于通过脚本从状态转移表自动生成。

3.3.3 常见误区与注意事项

• 矩阵维度错误：状态数或事件数统计遗漏，导致数组越界访问。
• 无效状态处理：矩阵中未定义的元素（如“不可能”组合）应填充为特殊值（如0xFF），并在执行引擎中增加保护判断。
• 可维护性下降：纯矩阵形式可读性差，建议保留状态转移表作为文档，矩阵由工具自动生成。

3.4 伪代码与数学形式化描述：从实现到验证的桥梁

3.4.1 伪代码表示法

伪代码（Pseudocode）是介于自然语言和编程语言之间的描述方式，用于表达FSM的执行逻辑。标准FSM伪代码框架包括：状态变量定义、事件处理循环、状态转移逻辑。典型结构如下：

// 电梯控制器FSM伪代码
enum State { IDLE, MOVE_UP, MOVE_DOWN, OPEN_DOOR, CLOSE_DOOR, FAULT };
State current_state = IDLE;

while (true) {
    Event evt = wait_for_event();  // 阻塞等待事件
    switch (current_state) {
        case IDLE:
            if (evt == CALL) {
                if (target_floor > current_floor) {
                    current_state = MOVE_UP;
                    motor_start();
                } else if (target_floor < current_floor) {
                    current_state = MOVE_DOWN;
                    motor_start();
                }
            } else if (evt == FAULT_SIG) {
                current_state = FAULT;
                alarm_on();
            }
            break;
        case MOVE_UP:
            if (evt == ARRIVE) {
                current_state = OPEN_DOOR;
                motor_stop();
                door_open();
            }
            break;
        // 其余状态处理类似...
    }
}

伪代码的优势在于贴近实现，可直接翻译为C/C++、Verilog或SystemVerilog代码。但需注意，伪代码容易引入实现细节，导致设计意图被淹没。建议在伪代码中保持状态转移逻辑的纯粹性，将具体硬件操作封装为函数调用。

3.4.2 数学形式化描述

FSM的数学形式化描述采用五元组定义：M = (S, Σ, δ, s₀, F)，其中：S 为有限状态集合；Σ 为有限输入事件集合（字母表）；δ: S × Σ → S 为状态转移函数；s₀ ∈ S 为初始状态；F ⊆ S 为接受状态集合（对于识别器）或输出函数集合（对于转换器）。对于Mealy机，还需定义输出函数 λ: S × Σ → O（O为输出集合）；对于Moore机，输出函数为 λ: S → O。数学形式化描述是形式化验证（如模型检验、等价性检查）的基础，工具如NuSMV、SPIN、UPPAAL均基于此类定义。

3.4.3 五种表示方法的对比与选择策略

3.5 综合案例：多表示方法在电梯控制器中的协同应用

为完整展示五种表示方法的协同工作，我们扩展电梯控制器场景：增加“超时保护”和“防夹检测”逻辑。初始现象：电梯在关门过程中检测到障碍物（事件：ObstacleDetected），需要立即重新开门。设计约束：关门超时（5秒）后若仍未关闭，则强制关门并发出警报。关键参数：关门超时定时器 T_close = 5s，开门保持时间 T_open = 3s。

分析判断过程：首先在状态转移图中增加“关门”状态的自环转移——收到ObstacleDetected事件时转移到“开门”状态并重置开门定时器；收到Timeout事件时执行强制关门动作并保持“关门”状态。然后更新状态转移表，在“关门”行增加两列：ObstacleDetected列填“OpenDoor/开门”，Timeout列填“CloseDoor/强制关门+报警”。接着更新状态矩阵，新增事件编号6=ObstacleDetected、7=Timeout，对应修改矩阵元素。伪代码中在CLOSE_DOOR分支增加事件处理。最后在数学形式化描述中，将状态转移函数δ扩展为 δ: S × Σ → S，其中Σ新增两个事件。

实际操作步骤与结果对比：在仿真环境中分别用状态转移图和状态转移表驱动同一测试用例集（包括正常关门、关门遇障碍、关门超时三种场景），两种表示方法产生的状态序列完全一致，验证了表示方法之间的等价性。但发现状态转移图在表达“关门超时”和“障碍物检测”两个事件同时到达时的优先级时存在歧义，而状态转移表通过单元格唯一性天然解决了该问题。这提示我们：当存在事件优先级或并发事件时，状态转移表比状态转移图更具优势。

风险与代价：增加超时和防夹逻辑后，状态数未增加（仍为6个），但事件数从6个增加到8个，状态矩阵从6×6扩展到6×8，存储空间增加约33%。在资源受限的MCU中，需评估ROM占用。此外，数学形式化模型的状态空间未变，但转移关系复杂度上升，模型检验时间可能增加。