有限状态自动机挑战有限状态自动机挑战

自动机是一种一旦启动，便能在无需人工干预的情况下回答特定问题的机器，例如：a + b 是否等于 c？

在本游戏中，我们将使用最简单的自动机模型——有限状态自动机（Finite State Automaton），来应对 80 个挑战。这些挑战源自字符串操作、二进制数以及日常生活。如果你对有限状态自动机不熟悉也不必担心；游戏内含教程，助你快速上手。此外，你也可以阅读以下介绍。
<h3>有限状态自动机</h3>有限状态自动机（FSA）是最简单的自动机类型。一个有限状态自动机由若干状态和转移规则组成。转移规则描述了状态何时转移到另一个状态。因此，它看起来像一张地铁线路图。有限状态自动机的“客户”是字符串。它决定哪些字符串被接受，哪些字符串被拒绝。例如，一个 FSA 可以接受有效的电子邮件地址、电话号码等。现在，让我们深入第一个示例：

它有两个状态：左侧的状态“1”和右侧的状态“2”。标记为绿色的“1”表示自动机从此处开始。标记为蓝色的“2”表示只有当自动机在此处停止并按顺序读取完输入字符串中的所有字符时，该字符串才会被接受。因此，这个自动机接受字符串 "a"，并拒绝任何其他字符串。

问题：请尝试自行设计一个接受 "ab" 的 FSA，以及一个接受 "a" 或 "b"（简写为 "a|b"）的 FSA（它们是游戏中的两个挑战）。

<h3>具有多种状态的有限状态自动机</h3>传统的有限状态自动机只有三种类型的状态：起始状态、接受状态和普通状态。在本游戏中，你可以在不同关卡中游玩具有不同状态定义的自动机。下图展示了一个示例。

<h3>非确定性</h3>FSA（以及其他自动机类型）最核心的概念被称为非确定性。为了引入这一概念，这里是第二个自动机示例。它接受所有以 'b' 结尾的字符串（仅由 'a' 和 'b' 组成）：

请在脑海中运行此自动机处理输入 "b"：(1) 它从 "1" 开始，执行 "1" 的自环，然后读取完 "b" 的所有字符并停在 "1"，因此拒绝 "b"；(2) 它从 "1" 开始并转移到 "2"，然后读取完 "b" 的所有字符并停在 "2"，因此接受 "b"。如果至少有一条执行轨迹结束于标记为蓝色的状态，则非确定性有限状态自动机（NFA）接受该字符串。

请在脑海中运行此自动机处理输入 "ab"：(1) 它从 "1" 开始，执行 "1" 的自环两次，然后读取完 "ab" 的所有字符并停在 "1"，因此拒绝 "ab"；(2) 它从 "1" 开始，执行 "1" 的自环一次，并转移到 "2"，然后读取完 "b" 的所有字符并停在 "2"，因此接受 "ab"。

非确定性至关重要，因为它允许 FSA 进行猜测，这使我们能够更自然（因为人类喜欢猜测）且快速地设计自动机。