1. 简介
在本文中，我们将学习状态机（State Machines）的基础知识及其在实际开发中的应用。
通过本文，你将掌握有限状态机的核心概念，了解其表示方式，并能将其用于建模实际系统的行为。
2. 状态机概述
有限状态机（Finite-State Machine, FSM）是自动机理论中的基础概念之一。它最初被设计用于描述一个系统的行为，这个行为依赖于一组有限的离散参数。
我们通常在以下情况下使用 FSM：
- 系统的行为定义清晰
- 参数的数量有限且可控
FSM 的每一个参数配置称为一个“状态”：
$$ S = {p_1, p_2, p_3, ..., p_n} $$
由于每个参数 $ p_i $ 的取值是有限的，因此整个系统可能的状态数也是有限的。例如，如果每个参数是二进制的（0 或 1），则总共有 $ 2^n $ 个不同的状态。
比如当 $ n = 2 $ 时：
$$ \text{Total States} = 2^2 = 4 $$
3. 状态转移规则
我们可以用 $ S_{k,t} $ 表示状态机在时间 $ t $ 时的状态。随着时间推移，我们会发现状态的变化往往具有某种规律性。
例如，一个状态可能永远不变：
$$ S_{k,t+1} = S_{k,t} \quad \forall t \in \mathbb{N} $$
但更常见的是，状态会在某些规则下发生转换：
如上图所示，该状态机在两个状态之间交替变化。
如果我们能完整理解这些转换规律，就可以将其建模为一组规则，用来决定状态的更新方式。因此，状态机不仅包括状态参数，还包括状态转换规则。
4. 状态机的表示方式
有限状态机可以根据是否与外部环境交互分为两类：
4.1 孤立系统（Moore Machine）
如果系统是孤立的，那么状态转换仅依赖于当前状态。例如：
$$ \begin{cases} S_1 \rightarrow S_2 \ S_2 \rightarrow S_1 \end{cases} $$
这种状态机称为 Moore 机，它不需要感知外部输入。
4.2 非孤立系统（Mealy Machine）
如果系统与外部环境交互，则状态转换由当前状态和输入共同决定。这种状态机称为 Mealy 机，典型例子是温控器（thermostat）。
温控器根据外部传感器读取的温度来改变自身状态：
5. 实际应用场景
我们日常使用的很多系统本质上都是状态机，只是我们不常这么称呼它们：
✅ 硬件设备：如个人电脑、智能手机、手持计算器
✅ 软件系统：如动画控制、游戏角色状态切换
✅ 文本处理：如正则表达式引擎内部使用状态机进行字符串匹配
5.1 游戏动画控制
游戏中的角色通常有多个动作状态（站立、行走、奔跑），这些状态之间的切换可以用 Mealy 机建模：
enum State {
STANDING, WALKING, RUNNING
}
class GameCharacter {
private State currentState;
public void update(Input input) {
switch (currentState) {
case STANDING:
if (input.isKeyPressed("LEFT") || input.isKeyPressed("RIGHT")) {
currentState = State.WALKING;
}
break;
case WALKING:
if (input.isKeyPressed("SHIFT")) {
currentState = State.RUNNING;
}
break;
case RUNNING:
if (!input.isKeyPressed("SHIFT")) {
currentState = State.WALKING;
}
break;
}
}
}
5.2 正则表达式引擎
正则表达式在编译阶段会被转换为有限状态机。它包含：
- 一个字符集（alphabet）
- 一组状态（包括初始状态）
- 一组接受状态（accepting states）
例如，正则表达式 a*b 对应的状态机如下：
6. 总结
本文我们学习了有限状态机的基本组成、表示方式及其应用场景。状态机是一种非常实用的建模工具，广泛应用于：
- 硬件设计
- 游戏开发
- 编译器与正则处理
- 工作流引擎（如 Spring State Machine）
掌握状态机的概念与实现方式，有助于我们在设计系统逻辑时更加清晰、高效。