欢迎来到有限状态机的世界！
在本章中，我们将深入探讨计算理论 (Theory of Computation)，重点研究有限状态机 (Finite State Machines, FSMs)。别被这个名称吓到了！其实，FSM 的本质非常简单，它只是一个“逻辑地图”，展示了系统如何根据发生的事件，从一个状态转换到另一个状态。
理解 FSM 至关重要，因为它们是计算机处理语言、红绿灯运行，甚至是电子游戏中 NPC（非玩家角色）决定下一步行动的基础。读完这些笔记后，你就能像专业人士一样绘制并解读这些“逻辑地图”了！
什么是有限状态机？
有限状态机 (Finite State Machine) 是一种计算的数学模型。让我们拆解这个名称来理解其实际含义：
1. 有限 (Finite)： 这意味着机器所处的状态数量是有限且固定的，它不可能有无穷多种选择。
2. 状态 (State)： 这是指机器在特定时刻的“情况”或“状态”。
3. 机器 (Machine)： 一个接收输入 (Input)，并根据当前状态决定下一步要移动到哪个状态的系统。
你知道吗？ 你的微波炉就是一个简单的 FSM！它有待机 (Idle)、烹饪 (Cooking) 和 暂停 (Paused) 等状态。按下“开始”按钮是一个输入，它会导致机器从待机转换 (Transition) 到烹饪状态。
必须记住的关键术语
• 状态 (State)： 一种特定的情况（例如：“已锁定”或“已解锁”）。
• 转换 (Transition)： 从一个状态移动到另一个状态的过程。
• 输入 (Input)： 触发转换的事件（例如：投入硬币）。
• 起始状态 (Initial State)： 机器开始运行的起点。
• 接受（终止）状态 (Accepting/Final State)： 代表“成功”或“有效”结果的状态。
可视化 FSM：状态转换图
展示 FSM 最常见的方法是使用状态转换图 (State Transition Diagram)。这是一张使用特定符号绘制的视觉地图。别担心，如果一开始觉得困难，只要熟悉了这些符号，读起来就像阅读流程图一样简单！
图表结构解析
• 圆圈： 代表状态。我们通常会在圆圈内写上状态名称（例如：\(S_0, S_1\)）。
• 箭头： 代表转换。它们显示了机器移动的方向。
• 箭头标签： 箭头上的文字是完成该移动所需的输入。
• “起始”箭头： 一个指向圆圈但没有起点的箭头，标识了起始状态。
• 双圆圈： 圆圈内还有一个圆圈，代表接受状态。如果处理完所有输入后机器停在这里，则该输入序列即被接受 (Accepted)。
现实生活中的例子：简单闸门
想象一个通常处于已锁定 (Locked) 状态的安全闸门。
1. 如果你在已锁定时推它，它会保持已锁定。
2. 如果你投入一枚硬币 (Coin)，它会移动到已解锁 (Unlocked) 状态。
3. 如果你在已解锁时推 (Push) 它，它会打开，然后变回已锁定状态。
在这个例子中，已锁定和已解锁是状态。硬币和推则是输入。
复习小贴士： 记住双圆圈！这是学生最容易忘记的地方。它告诉我们机器已经达到了一个“有效”的结论。无输出的 FSM
在 AQA AS Level 的课程大纲中，我们特别关注无输出的 FSM（也称为有限状态自动机）。这些机器的任务很简单：决定一串符号序列是被接受 (Accepted) 还是拒绝 (Rejected)。
如何追踪 FSM（分步指南）
要判断一个序列（如“1101”）是否被接受，请执行以下步骤：
1. 从起始状态开始（寻找那个没有起点的箭头）。
2. 读取输入字符串的第一个符号。
3. 沿着与该符号匹配的箭头移动到下一个状态。
4. 对字符串中的每个符号重复此步骤。
5. 检查最终位置： 当所有符号处理完毕后，如果你停在一个双圆圈状态，则该字符串被接受。否则，它将被拒绝。
要避免的常见错误
“死胡同”陷阱： 有时某个状态对于特定的输入没有对应的转换（例如：你处于状态 A，输入为 '1'，但没有标记为 '1' 的箭头）。在许多简单的 FSM 中，如果没有有效的移动路径，机器会“崩溃”，该输入会立即被拒绝。
关键总结： 无输出的 FSM 就像是“接受检测器”。它们只关心你最终是否停在正确的位置（双圆圈）。状态转换表
有时，如果状态太多，绘制图表会变得很混乱。这时就需要状态转换表 (State Transition Table)。它包含完全相同的信息，只是以网格形式呈现！
如何阅读/建立表格
• 横列 (Rows) 代表当前状态。
• 直栏 (Columns) 代表接收到的输入。
• 单元格 (Cells) 告诉你下一个状态。
例如，表格看起来像这样：
当前状态 | 输入: 0 | 输入: 1
------------------------------------
S0 (起始) | S0 | S1
S1 (终止) | S0 | S1
这张表告诉我们：“如果你处于 S0 并收到 1，请移至 S1。”
记忆法： “如果-而且-那么”规则
要记住如何使用表格，只需说：“如果 (IF) 我处于这个状态，而且 (AND) 我得到这个输入，那么 (THEN) 我就移动到那个状态。”
计算理论总结：FSM
• FSM 是具有有限数量状态的系统模型。
• 转换由输入触发。
• 状态转换图是视觉地图；状态转换表是网格。
• 起始状态 = 没有起点的箭头。接受状态 = 双圆圈。
• 对于无输出的 FSM，机器只有在结束于接受状态时才会接受字符串。
如果觉得这些概念很抽象，不用担心！掌握 FSM 的最好方法就是练习为简单的任务绘制它们，例如建立一个只接受以 '1' 结尾的二进制数字的机器。你一定做得到的！