计算理论：正则表达式与正则语言
你好！欢迎来到计算理论中最实用且最令人着迷的领域之一：正则表达式 (Regular Expressions)。
如果这个名称听起来有些深奥，别担心。简单来说，正则表达式（常简称为“Regex”或“RE”）就是一种极其强大的工具，用于描述和匹配文本字符串中的模式。
如果你曾经在文字处理软件中使用过“查找和替换”功能，或者在注册网站时校验过电子邮箱地址的合法性，那么你其实已经见过正则表达式在实际工作了！
在本章中，我们将学习如何编写这些模式，并理解它们与最简单的抽象计算模型——有限状态机 (Finite State Machine, FSM) 之间的深刻联系。
1. 理解正则语言
什么是计算机科学中的“语言”？
在计算理论的语境下，语言 (Language) 仅仅是由特定的字母表 (Alphabet) 组成的合法字符串（字符序列）集合。
- 示例： 如果字母表是 \(\{0, 1\}\)，那么一种语言可能是所有以 0 开头的字符串的集合（例如：0, 01, 000, 0101...）。
正则语言 (Regular Language) 是指能够使用正则表达式精确描述，或者能够被有限状态机 (FSM) 所识别的语言。这是我们在该领域研究的最基础的一类语言。
什么是正则表达式 (RE)？
正则表达式是一个定义搜索模式的正式字符序列。你可以把它看作是合法字符串的“蓝图”。
类比： 想象你正在数据库中查找每一块车牌。虽然你不知道具体的牌照号码，但你了解其模式：三个字母，后跟两个数字，再后跟一个字母。正则表达式就是你定义这一特定模式的方法。
关键结论： 如果一个模式可以用正则表达式描述，那么它就属于正则语言。
2. 基本元字符（构建模块）
为了编写 RE，我们使用标准字符（如 'a', '1', '@'）结合称为元字符 (Metacharacters) 的特殊字符。这些元字符定义了重复和选择的规则。
在以下示例中，我们将使用字母表 \(\{a, b, c\}\)。
2.1 重复与可选性
这些元字符控制前导字符或组允许出现的次数。
1. 克莱尼星号 (Kleene Star)：*（零次或多次重复）
元字符 * 表示其前面的元素可以出现零次或多次。它或许是最基本的重复运算符。
-
RE：
a*
匹配： "" (空字符串), "a", "aa", "aaa", "aaaaa"... -
RE：
b(a)*
匹配： "b" (当a重复 0 次时), "ba", "baa", "baaa"...
记忆小贴士： * 看起来像雪花——它可以覆盖零空间（空）也可以覆盖大量空间（无限重复）。
2. 加号：+（一次或多次重复）
元字符 + 表示其前面的元素必须出现一次或多次。它类似于 *，但它不能匹配空字符串。
-
RE：
a+
匹配： "a", "aa", "aaa"... (但不能匹配空字符串 "") -
RE：
a(bc)+
匹配： "abc", "abcbc", "abcbcbc"...
3. 问号：?（可选/零次或一次重复）
元字符 ? 表示其前面的元素是可选的。它出现零次或一次。
-
RE：
colou?r
匹配： "color" 或 "colour"（非常适合处理不同的拼写方式！） -
RE：
a(b)?c
匹配： "ac" 或 "abc"
2.2 选择与分组
4. 选择/或运算符：|
元字符 | 用于指定选择 (Alternation)，意为“这个或那个”。它在两个或多个表达式之间提供一种选择。
-
RE：
cat|dog
匹配： 完全匹配 "cat" 或完全匹配 "dog"。 -
RE：
a(b|c)d
匹配： "abd" 或 "acd"。
5. 分组：()
圆括号 () 用于将正则表达式分组，以便将重复或选择运算符应用于整个组。
-
如果你写
ab+，+仅作用于字符 'b' (a, abb, abbb...)。 -
如果你写
(ab)+，+作用于整个组 'ab' (ab, abab, ababab...)。
示例：匹配具有特定扩展名的简单文件名。
RE： (data|file).txt
匹配： "data.txt" 或 "file.txt"
✎ 快速回顾：元字符含义
*: 零次或多次+: 一次或多次?: 零次或一次（可选）|: 或 (选择)(): 分组
3. 字符类
字符类允许你为字符串中的单个位置指定一组可接受的字符。这些类使用方括号 [] 定义。
1. 特定字符集
将字符放在括号内表示“匹配该集合中的任何单个字符”。
-
RE：
[aeiou]
匹配： 任何单个元音字母（如 'a', 'e', 'i', 'o' 或 'u'）。 -
RE：
[CH]at
匹配： "Chat" 或 "Hat"。（教学大纲指定使用此格式。）
2. 字符范围
若要指定大范围的字符（例如所有数字或所有大写字母）而无需逐一列出，可以使用连字符 -。
-
RE：
[0-9]
匹配： 0 到 9 之间的任何单个数字。 -
RE：
[A-Z]
匹配： A 到 Z 之间的任何单个大写字母。 -
RE：
[a-zA-Z0-9]+
匹配： 字母（大写或小写）和数字的任意组合，长度至少为 1。
你知道吗？ 正则表达式对于词法分析 (Lexical Analysis)（编译器的第一阶段）至关重要，在编译过程中，它们被用于识别关键字、标识符和数字等记号 (Tokens)。
正则表达式构建示例
让我们构建一个符合英国邮政编码结构的 RE，其规则为：一个字母，后跟零个或多个数字，再后跟一个必须的空格，最后跟一个或多个字母。
由于结构要求较复杂，根据教学大纲，我们简化为描述一个简单的标识符：变量名必须以字母开头，之后可以包含字母或数字。
- 必须以字母开头：
[a-zA-Z] - 其后跟零次或多次出现的字母或数字：
[a-zA-Z0-9]*
组合 RE： [a-zA-Z][a-zA-Z0-9]*
- 匹配： "X", "Var1", "myVariable", "count3"
- 不匹配： "1X", "345"
应避免的常见错误： 混淆 a|b* 和 (a|b)*。
前者匹配 'a' 或 零/多次出现的 'b' (例如 'a', 'b', 'bb', 'bbb')。
后者匹配由 'a' 和 'b' 组成的任何序列，包括空字符串 (例如 'ab', 'aba', 'baab')。分组至关重要！
4. 理论联系：FSM 与正则语言
本节将正式理论重新引入我们的讨论。在计算理论中，有限状态机 (FSM) 是最简单的计算模型。
4.1 等价原则
这里最重要的概念是 RE 与 FSM 之间的关系：
正则表达式和 FSM 是定义正则语言的等价方式。
这意味着，对于你编写的每一个正则表达式，你都可以设计一个对应的 FSM（状态转换图），它接受完全相同的字符串集合。反之，对于任何 FSM，你也可以编写一个正则表达式来描述它所识别的语言。
- 如果一种语言可以由正则表达式表示，那么它就是一种正则语言。
- 如果一种语言可以由 FSM 识别，那么它就是一种正则语言。
4.2 从 FSM 编写 RE
你必须能够编写一个识别与给定 FSM 相同语言的正则表达式，反之亦然：设计一个识别与给定正则表达式相同语言的 FSM。
示例：从简单的 FSM 编写 RE。
想象一个 FSM，它接受以下形式的字符串：一个 'a'，后跟任意数量的 'b'，最后跟一个 'c'。
- FSM 从状态 S0 开始。
- 输入 'a' 后，从 S0 唯一的转移路径进入 S1。
- S1 在输入 'b' 时循环回到自身。
- 从 S1 输入 'c' 后进入最终（接受）状态 S2。
逐步构建：
- 字符串必须以 'a' 开头。(
a) - 'b' 可以重复零次或多次（S1 上的循环）。(
b*) - 字符串必须以 'c' 结尾。(
c)
最终的正则表达式为： ab*c
示例 2：使用选择符
想象一个 FSM，它接受以 '0' 或 '1' 开头，后跟任意数量 '0' 的字符串。
RE： (0|1)0*
这可以匹配 "0", "1", "000", "10", "1000" 等。
为什么这很重要？
FSM 与 RE 之间的等价性是许多实用计算应用的基础，尤其是在解析、搜索和校验数据结构方面。如果你能用 RE 定义一个模式，你就知道可以使用一个简单高效的 FSM 来完成计算。
💯 考试要点总结
你必须熟练掌握：
- 理解并应用五个关键元字符：
*,+,?,|, 和()。 - 使用字符类（例如
[A-Z]或[0-9]）来表示字符集合。 - 陈述其形式关系：正则表达式和 FSM 描述了同一类语言（正则语言）。
- 在 FSM 图/描述与对应的正则表达式之间进行简单的转换。