Finite state machines (FSMs)

理解有限状态机 (Finite State Machines, FSMs)

你好！欢迎来到计算理论 (Theory of Computation) 这一章。计算机科学的这一领域旨在研究计算机能够解决哪些问题，以及我们如何对这些计算过程进行建模。如果听起来有些抽象，请不要担心——我们将从最简单、最直观的计算模型开始：有限状态机 (FSM)。

无论你是否意识到，你每天都在与 FSM 打交道！从交通灯到密码验证，它们是简单系统行为背后的数学基石。

什么是有限状态机 (FSM)？

有限状态机 (FSM)，有时也被称为有限自动机 (Finite Automaton, FA)，是一种数学模型，用于设计那些仅具备有限、固定数量的操作条件或“状态”的系统。

类比：想象一个交通灯。它只能处于三种状态之一：红灯、红黄灯或绿灯。它不能同时处于红灯和绿灯状态。状态之间的转换由输入（如定时器）触发。

FSM 的核心组成部分

一个 FSM 必须包含四个主要部分：

• 状态 (States)： 机器所能处于的有限组条件或配置。
• 起始状态 (Start State)： 机器开始运行时所处的初始状态。
• 输入字母表 (Input Alphabet)： 机器可以接收的一组有限符号（或事件）。它们触发状态之间的转换。
• 转换 (Transitions)： 指定机器如何根据接收到的输入从一个状态移动到另一个状态的规则。

核心要点： FSM 是由固定的、有限数量的状态以及状态间的转换规则所定义的简单机器。它们是无记忆的（只关心当前状态和当前输入）。

表示有限状态机

我们有两种主要方式来正式描述 FSM：使用图表（可视化）和使用表格（结构化）。你必须能够绘制并解读这两者。

1. 状态转换图 (State Transition Diagrams)

这是可视化 FSM 最直观的方法。

• 状态用圆圈或节点表示。
• 起始状态由一个指向该状态的孤立箭头标示。
• 转换（状态间的移动）用连接状态的箭头表示。
• 每个转换箭头都标有触发该移动的输入符号。
• 如果 FSM 用于识别（如验证密码），我们可能会使用接受/终止状态 (Accept/Halting States)，通常用双圆圈表示。

示例：一个简单的 FSM，用于检查输入字符串是否包含连续的两个 '1'。

如果状态 A 是起始状态，状态 C 是接受状态，那么从 A 到 B 的箭头可以标记为 '1'，从 B 到 C 的箭头也可以标记为 '1'。

2. 状态转换表 (State Transition Tables - 正式视图)

状态转换表以正式的表格格式展示了与图表相同的信息。这对于检查所有可能的情况非常有效。

• 行通常代表当前状态。
• 列通常代表输入符号。
• 表格中的条目指定了下一状态。

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

教学大纲要求你理解能够产生输出的 FSM。关键点是，你只需要了解米利机 (Mealy Machines)。

在米利机中，输出是在转换过程中生成的。

输出取决于： (当前状态) 和 (接收到的输入)

记忆小贴士： 记住 'M' 代表 Movement（移动）。米利机的输出发生在“移动”（转换）的那一刻。

在标注米利机的转换图或表格时，标签格式如下：

输入 / 输出

转换示例： 如果 FSM 处于状态 S1 且收到输入 'a'，它移动到 S2 并输出 '0'。
图表标签：a / 0

核心要点： FSM 可以通过图表（可视化）或表格（正式）进行建模。对于带输出的机器，请记住米利机规则：输出与特定的输入/转换相关联。

正则表达式与正则语言

有限状态机是一种计算模型。正则表达式 (Regular Expressions, REs) 是一种描述这些 FSM 所能识别的字符串集合（即语言）的方法。它们在编程中非常有用，常用于数据验证、文本搜索和检查输入格式。

什么是正则语言？

正则语言 (Regular Language) 是指任何可以通过正则表达式定义或被FSM识别的字符串集合。

你知道吗？几乎所有现代编程语言（Python, Java 等）都使用正则表达式进行模式匹配！

元字符：正则表达式的构建块

正则表达式使用特殊符号（元字符）来简洁地描述模式。你必须熟悉以下符号：

重复与可选性

• * (克林星号 Kleene Star)： 匹配前一个元素零次或多次重复。
  • 示例： A* 匹配 "", "A", "AA", "AAA" 等。
  • 记忆小贴士： 星号意味着“完全可选，也许有很多次”。
• + (克林加号 Kleene Plus)： 匹配前一个元素一次或多次重复。
  • 示例： A+ 匹配 "A", "AA", "AAA" 等，但不匹配 ""。
  • 记忆小贴士： 加号意味着“至少一次”。
• ? (可选)： 匹配零次或一次重复（前一个元素是可选的）。
  • 示例： Colou?r 同时匹配 "Color"（美式拼写）和 "Colour"（英式拼写）。

分组与选择

• | (交替或 OR)： 匹配符号左侧的表达式或右侧的表达式。
  • 示例： Cat|Dog 匹配字符串 "Cat" 或字符串 "Dog"。
• () (分组)： 用于将正则表达式组合在一起，以便元字符（如 * 或 +）应用于整个组。
  • 示例： (AB)+ 匹配 "AB", "ABAB", "ABABAB" 等。（如果我们写 AB+，它将匹配 'A' 后面跟着一个或多个 'B'）。

字符类

字符类允许你指定在特定位置可以匹配的一组字符。

• 直接选择： [CH] 匹配字符 'C' 或 'H'。
• 范围选择： [A-Z] 匹配 A 到 Z 之间的任何单个大写字母（包含边界）。

常见错误： 确保你理解 *（零次或多次）和 +（一次或多次）之间的区别。如果语言要求某个字符至少出现一次，请使用 +。

核心要点： 正则表达式是强大的模式描述工具。请务必掌握元字符（特别是 *, +, ?, |），因为它们是定义正则语言的基础。

FSM 与正则表达式之间的关系

这是本章最重要的理论概念之一：

正则表达式和 FSM 是定义正则语言的等价方式。

这意味着，如果你能画出一个识别某种模式的 FSM，你一定可以写出一个描述该模式的正则表达式，反之亦然。

应用等价性

在考试中，你可能需要在这两种模型之间进行转换：

1. 从 FSM 到正则表达式 (RE)

你需要追踪从起始状态到接受状态的 FSM 路径，使用元字符来表示循环和选择。

• 任务： 写出一个描述给定 FSM 所识别语言的正则表达式。
• 示例 FSM： 识别偶数个 '1'（起始于 S0，输入 '0' 时保持在 S0，输入 '1' 时移动到 S1。输入 '1' 时回到 S0，输入 '0' 时保持在 S1）。S0 是接受状态。
• 对应的 RE： (0*10*1)*0*
  • 解释： 任意数量的 0 (0*)，后面跟着一对被任意数量 0 分隔的 1 (10*1)。整个模式必须重复零次或多次 (...) * 以确保 '1' 的数量为偶数，最后以任意数量的 0 (0*) 结尾。

2. 从正则表达式到 FSM 设计

你需要设计必要的状态和转换，以准确实现 RE 定义的逻辑。

• 任务： 设计一个 FSM 来识别与给定 RE 相同的语言。
• 示例 RE： A(B|C)*（匹配一个 'A'，后面跟着零个或多个 'B' 或 'C' 的序列）。
• FSM 设计步骤：
  1. 创建一个起始状态 (S0)。
  2. 从 S0 的转换必须是 'A'，以到达下一个逻辑状态 (S1)。
  3. S1 必须处理 (B|C)* 部分。由于这意味着 'B' 或 'C' 出现零次或多次，S1 必须是最终的接受状态，并且在接收到输入 'B' 或 'C' 时必须回跳到自身。
  4. 你会画出从 S1 指向 S1 的箭头，分别标记为 'B' 和 'C'。

重要意义

此处的关键在于了解正则原则 (Regularity Principle)：

一种语言是正则的，当且仅当它能被 FSM 识别。由于 FSM 和 RE 是等价的，这意味着如果你看到一个 RE，你就可以确定有一个简单的 FSM 可以处理它。

核心要点： FSM 和正则表达式可以互换。它们定义了同一类简单的语言——正则语言。你必须多加练习，熟练掌握这两种形式之间的转换。