欢迎来到正则语言的世界！
你好！今天，我们要深入探讨计算理论 (Theory of Computation) 中一个引人入胜的领域：正则语言 (Regular Languages)。别担心，如果起初觉得有些抽象——你可以将这章节想象成学习计算机用来识别规律的“语法”。无论是自动售货机判断你投入的零钱是否足够，还是搜索引擎在文件中寻找特定词汇，正则语言都在背后默默运作。让我们一步步拆解吧！
1. 有限状态机 (Finite State Machines, FSMs)
在讨论语言之前，我们必须先了解负责读取它们的“机器”。有限状态机 (FSM) 是一个简单的计算模型。它具有有限 (finite) 的状态数量，并根据输入在这些状态之间切换。
不带输出的 FSM
这些机器就像“是非题”裁判。它们读取一串符号，最后告诉你这串符号是被接受 (accepted) 还是被拒绝 (rejected)。
• 起始状态 (Start State)： 由一条从无指向它的箭头表示。
• 接受状态 (Accepting State)： 由双圈表示。如果你最终停在这里，机器就会“接受”该输入。
带输出的 FSM：米利机 (Mealy Machines)
米利机 (Mealy Machine) 是一种特殊的 FSM，它会为每一次转换提供输出。
类比：想象一台自动售货机。当你投入“一英镑硬币”时，机器不仅仅是改变状态，它可能会“输出”一则显示信息，例如“请选择饮料”。
表示 FSM 的方法
我们可以用两种方式展示 FSM 的运作：
1. 状态转移图 (State Transition Diagrams)： 使用圆圈（状态）和箭头（转换）组成的视觉化地图。
2. 状态转移表 (State Transition Tables)： 一个显示当前状态、输入以及下一个状态将是什么的表格。
快速复习箱：
• FSM： 拥有固定数量状态的机器。
• 接受状态： 终点目标！代表输入字符串是有效的。
• 米利机： 会产生输出的 FSM。
2. 正则表达式的数学基础：集合 (Sets)
要理解正则语言，我们需要学习集合的语言。集合只是一组无序的项目组合。
重要的集合记号
• \( A = \{1, 2, 3\} \)： 包含数字 1、2 和 3 的集合。
• \( \emptyset \)： 空集合 (empty set)（内部没有任何元素的集合）。
• \( x \in \mathbb{N} \)： 这意味着“\( x \) 是自然数集合的成员”（0, 1, 2, 3...）。
• \( | \)： 这个符号意思是“使得 (such that)”。例如，\( \{x | x > 5\} \) 意指“所有 \( x \) 的集合，使得 \( x \) 大于 5”。
集合类型
• 有限集合 (Finite Set)： 你可以数出里面的元素（例如：班上的学生人数）。
• 无限集合 (Infinite Set)： 数量无穷无尽（例如：所有偶数的集合）。
• 可数无限集合 (Countably Infinite Set)： 一种无限集合，只要你有足够的时间，理论上可以将元素一个一个“数”出来（例如自然数 \( \mathbb{N} \)）。
集合运算
将这些想成“群体的数学运算”：
• 并集 (\( \cup \))： 将两个集合合并。
• 交集 (\( \cap \))： 只找出同时出现在两个集合中的项目。
• 差集 (\( \backslash \) 或 \( - \))： 取出第一个集合，并减去同时也在第二个集合中的任何元素。
你知道吗？
笛卡尔积 (Cartesian Product) (\( X \times Y \)) 是一种将一个集合中的每个元素与另一个集合中的每个元素配对的方法。如果集合 X 是 {红色, 蓝色} 而集合 Y 是 {汽车, 单车}，那么乘积就是 {(红色, 汽车), (红色, 单车), (蓝色, 汽车), (蓝色, 单车)}。
重点总结： 集合是基础构建块。只要你知道如何分组项目并使用像 \( \in \)（属于）和 \( \cup \)（并集）这样的符号，你就已经成功了一半！
3. 正则表达式 (Regular Expressions, RegEx)
正则表达式 (RegEx) 是描述字符串集合的一种简写方式。我们不需要列出所有可能的有效字符串，而是使用一种模式 (pattern) 来表示。
元字符 (你的 RegEx 工具箱)
• \( * \) (Kleene 星号)： 0 次或多次重复。（例如：\( a* \) 代表“”，“a”，“aa”，“aaa”...）
• \( + \)： 1 次或多次重复。（例如：\( a+ \) 代表“a”，“aa”，“aaa”...）
• \( ? \)： 0 次或 1 次重复——基本上就是让该字符变成可选的 (optional)。
• \( | \) (选择)： 意指“或”。(例如：\( a|b \) 代表“a”或“b”)
• \( ( ) \)： 用于将表达式的部分组合在一起。
示例：表达式 \( a(b|c)* \) 描述了以“a”开头，后面接任意数量“b”或“c”的字符串。这可以是“a”、“ab”、“ac”、“abbc”等等。
要避免的常见错误： 不要混淆 \( * \) 和 \( + \)。记住：星号 (Star) 可以是空值（\( * \) 包含空字符串），但加号 (Plus) 至少必须有一个。
重点总结： RegEx 只是字符串的“搜索模式”。如果你能写出一个模式，你就能定义一个语言！
4. 定义“正则语言”
这是“顿悟”的时刻，一切都串联起来了。
如果一个语言满足以下条件，我们就称它为正则语言 (Regular Language)：
1. 它可以用一个正则表达式来表示。
或者
2. 它可以用一个有限状态机 (FSM) 来识别。
等价规则
FSM 和正则表达式是等价的。 这意味着如果你能画出一个 FSM 来识别某个模式，你就能为它写出一个 RegEx，反之亦然。它们只是完成同一项工作的两种不同方式！
类比：这就像食谱。一个人可能把它写成一系列步骤（FSM），而另一个人可能将其写成配料的数学公式（RegEx）。外观不同，但做出来的蛋糕是一样的！
快速复习：
• 如果 RegEx 可以描述它，它就是正则的。
• 如果 FSM 可以接受它，它就是正则的。
• RegEx \( \equiv \) FSM。
总结：融会贯通
我们今天涵盖了很多内容！这就是“全貌”：
• FSMs 是处理输入的机器。
• 集合为这些输入的外观提供了数学规则。
• 正则表达式是我们用来定义语言的简写模式。
• 如果一个 FSM 或 RegEx 适用于某种语言，那么该语言在官方定义上就是正则的。
如果需要多读几遍也没关系。计算理论就像一场拼图游戏——一旦 FSM 和 RegEx 的碎片拼凑在一起，你就会发现规律无处不在！你一定可以做到的！