Finite state machines (FSMs)

有限状态机 (FSM) 简介

欢迎来到计算机科学中最合乎逻辑且令人满足的部分！你有没有想过自动售货机是怎么知道你投的钱足够了？或者简单的交通灯是怎么知道何时该变换灯号的呢？它们运作的基础就是有限状态机 (Finite State Machine, FSM)。

在这一章，我们将学习如何根据输入来模拟从一个“状态”转换到另一个“状态”的系统。如果一开始听起来有点技术性，别担心——它本质上就是一张展示系统运作方式的地图！读完这些笔记后，你将能够绘制这些地图，甚至利用它们来设计简单的计算机逻辑。

什么是有限状态机？

从核心本质来看，FSM 是一种运算的数学模型。这是一个在任何特定时间点，都只能处于有限数量之状态中其中一个的系统。

类比：电灯开关
想象一个普通的电灯开关。它拥有“有限”数量的状态：它不是开 (ON) 就是关 (OFF)。它不可能同时处于两者之间，也不可能处于两者中间的状态。当你拨动开关（即输入）时，状态就会改变。如果是关，它就会变开；如果是开，它就会变关。

FSM 的关键组成部分

要了解 FSM，你需要知道以下四点：
1. 状态 (States)： 机器可能处于的不同状况（通常以圆圈表示）。
2. 输入 (Inputs)： 导致状态变化的事件或触发因素。
3. 转换 (Transitions)： 从一个状态移动到另一个状态的过程（以箭头表示）。
4. 输出 (Outputs)： 机器产生的结果（仅在特定类型的 FSM 中存在）。

快速复习： FSM 就像是简单机器的一个“大脑”。它记得自己身处何处（状态），并等待推动力（输入）来移动到别处。

状态转换图 (State Transition Diagrams)

状态转换图是我们绘制 FSM 的可视化方式，看起来就像是一组由箭头连接的圆圈。

如何阅读图表：

• 圆圈： 每个圆圈代表一个状态。状态名称通常写在圈内。
• 起始箭头： 一个从“虚无”指向某个圆圈的箭头，标示了初始状态 (Initial State)（即起点）。
• 箭头： 这些是转换。它们显示机器在接收输入时的移动方向。触发该移动的输入会写在箭头上。
• 双圆圈： 带有双边框的圆圈是接受状态 (Accepting State)（或结束状态）。这意味着机器已成功完成其任务。

示例：一个简单的 FSM，用于检查二进制字符串是否以 '1' 开头。
1. 从 状态 S0（初始状态）开始。
2. 如果输入是 '1'，则沿着箭头移动到 状态 S1（接受状态）。
3. 如果输入是 '0'，则沿着箭头移动到 状态 S2（拒绝状态）。

常见错误： 忘记标记箭头！没有标签的话，我们就不知道哪个输入会导致什么变化。

状态转换表 (State Transition Tables)

有时，如果状态太多，图表可能会变得混乱。在这种情况下，我们会使用状态转换表。这只是一个网格，它以文本格式提供了与图表完全相同的信息。

表格结构：
• 左侧栏位列出当前状态 (Current State)。
• 顶部列出所有可能的输入 (Inputs)。
• 中间的单元格则告诉你下一个状态 (Next State)。

示例表格：
当前状态 | 输入：0 | 输入：1
S0 | S0 | S1
S1 | S0 | S1

在此表中，如果你处于状态 S0 并收到 1，你就会转移到 S1。

关键要点： 图表非常适合观察“流程”，而表格则适合用来确保你没有遗漏每个状态下任何可能的输入！

带输出的 FSM：米利机 (Mealy Machines)

我们目前讨论的 FSM 只是简单地“接受”或“拒绝”一个序列。然而，牛津 AQA 学生也需要了解米利机 (Mealy Machines)。这些 FSM 会根据当前状态和输入产生输出。

在米利机图表中，箭头标记为 输入 / 输出。

示例：自动售货机
想象一台需要存入 20 分钱的机器。
• 状态：0 分。输入：10 分。转换：移动到“10 分”状态。输出：“显示 10”。
• 状态：10 分。输入：10 分。转换：移动到“就绪”状态。输出：“释放饮料”。

数学注释： 输出由转换决定。我们将其写作 \( 输入 / 输出 \)。

你知道吗？ 米利机以 George H. Mealy 的名字命名，他是贝尔实验室 (Bell Labs) 的先驱，协助开发了早期电信系统的这些概念！

总结与成功秘诀

建立 FSM 的步骤：

1. 识别状态： 系统可能处于哪些不同的“状况”？
2. 识别输入： 什么会发生并改变这些状况？
3. 绘制转换： 对于每一个状态，决定当每一个可能的输入发生时会发生什么。
4. 定义开始/结束： 清晰标示流程从哪里开始，以及在哪里成功结束。

记忆法：S.I.T. 规则

为了保持简单，记住 S.I.T.：
S (State) - 状态（我现在在哪里？）
I (Input) - 输入（刚发生了什么事？）
T (Transition) - 转换（我现在要去哪里？）

最终快速复习：

• 有限 (Finite)： 状态数量是有限的。
• 确定性 (Deterministic)： 在你学习的 FSM 中，对于任何状态和输入，都有且只有一个下一个状态。
• 状态转换图： 可视化的地图（圆圈和箭头）。
• 状态转换表： 地图的网格版本。
• 米利机： 对每个转换都会给出输出的 FSM。

如果一开始觉得很棘手，别担心！试着为简单的东西画一个 FSM，例如微波炉（状态：闲置、加热中、暂停）。一旦你能可视化状态之间的移动，这些图表就会变得像直觉一样简单！