第 4 章 · 01 理论起点:正则与有限自动机

第 4 章 · 01 理论起点:正则与有限自动机

本节摘要:这是第 4 章的认知地基。正则表达式看起来像「玄学咒语」,但它在数学上有一个优雅的对应:每个正则表达式等价于一个「有限自动机」(finite automaton)——一种在状态之间转移、根据输入决定接受或拒绝的简单机器。本节要建立这个对应关系:正则是「描述语言」,自动机是「执行机器」,两者等价。理解了这个理论起点,后续的 Thompson 构造(把正则编译成自动机)才不会是空中楼阁。

内容来源:基于「Build your own X」Regex Engine 域相关条目与正则理论整理的导读。

学习目标

阅读完本节,你应当能够:

1. 说清「正则表达式」与「正则语言」在数学上的对应关系。
2. 用一个简单例子解释「有限自动机」:状态、转移、接受状态。
3. 理解「正则 = 有限自动机能识别的语言」这个等价定理的含义。
4. 说清为什么这个理论起点重要(它把「模糊的描述」变成「可执行的机器」)。

一、学习价值:理论是后续一切的根基

造正则引擎,有人会想「直接写代码不就行了,学什么理论?」——这是最容易卡住的误区。正则引擎的每个算法(NFA 构造、子集构造、回溯),都建立在「正则 = 自动机」这个理论等价上。不懂理论,你会沦为「照抄别人的代码却不知道为什么」;懂了理论,你能自己推导出每个算法。

这个理论其实不复杂——它就是「正则表达式」与「有限自动机」之间的一个数学等价定理。理解它,你就能把「一段正则描述」翻译成「一台能跑的机器」。

二、认知拆解:正则、语言、自动机

正则表达式描述「语言」

在形式语言理论里,一个正则表达式描述的是一组字符串——也就是一个「语言」。比如正则 ab*c 描述的语言是:{ac, abc, abbc, abbbc, ...}(a 后面跟任意个 b,再跟 c)。

有限自动机识别「语言」

有限自动机(finite automaton)是一个简单的计算模型:

        b           b           c
(0) ──────► (1) ──────► (2) ──────► ((3))
 a                                    接受!
​

它有几个要素:

• 状态(圆圈):机器当前在哪个状态。
• 转移(箭头):在某状态读到某输入,跳到另一状态。
• 起始状态:机器开始的状态(带入箭头的)。
• 接受状态:读完整段输入后,若停在接受状态(双圈),则「接受」这串输入(即它属于这台机器识别的语言)。

上面这台机器,识别的就是 ab*c 这个正则描述的语言——从状态 0 读 a 到 1,读若干 b 在 1 循环,读 c 到接受状态 3。

伟大的等价定理

形式语言理论有一个核心定理:「正则表达式描述的语言」=「有限自动机能识别的语言」。换句话说,任何能用正则描述的字符串集合,都能造一台有限自动机来识别它;反之亦然。

这个等价定理的意义在于:它把「正则」与「机器」绑定了。你想让计算机处理一段正则,不用「猜」,只要按算法把正则翻译成对应的自动机,然后用自动机跑输入文本即可。这个翻译算法,就是下一节讲的 Thompson 构造。

三、上手第一步:画几个自动机找感觉

在写代码之前,先用纸笔画几个简单自动机,建立直觉:

1. 画识别 a 的自动机(最简单:两状态,a 转移到接受)。
2. 画识别 a*(任意个 a)的:接受状态带自环。
3. 画识别 ab 的:三状态线性。
4. 画识别 a|b(a 或 b)的:一个状态分叉到两条路径。

画完这几个,你会对「正则 ↔ 自动机」的对应有直观感觉。这种直觉是后续学 Thompson 构造法的基础。

本节要点回顾

1. 正则表达式描述一组字符串(一个「语言」);有限自动机识别一个语言——两者数学上等价。
2. 有限自动机要素:状态、转移、起始状态、接受状态。
3. 核心等价定理:「正则描述的语言」=「有限自动机能识别的语言」,这是造正则引擎的理论根基。
4. 理论的价值:把「模糊的正则描述」变成「可执行的机器」,后续算法(Thompson 构造等)都建立其上。

推荐上手顺序

1. 先用纸笔画几个简单正则(a、a*、ab、a|b)对应的自动机,建立直觉。
2. 读下一节(02 NFA vs DFA),理解自动机的两种类型。
3. 读第 03 节 Thompson 构造,看如何系统地把任意正则编译成自动机。
4. 理论吃透后,再动手写代码(第 05、06 节)。

下一节讲自动机的两种类型——NFA(非确定)与 DFA(确定),以及它们的取舍。