Regular Expression 从理论到实现 - I

前言

本篇文章是 Regular Expression 从理论到实践系列 的第一篇文章。

在这个系列里，我将尝试从理论出发，阐述 Regular expression 作为软件开发人员不可或缺的工具背后所蕴含的计算机科学的重要理论，以及如何将这些理论付诸实践（用代码实现）。

或许对大多数开发者来说，掌握一门称手的工具更为重要。但是我希望读者们读完本系列文章之后，也能意识到理论的重要之处。

虽然我们已经习惯于各种工具所带来的爆炸式的生产力提升，但在计算机科学的领域中，真正指导人们创造出这些工具的理论，往往受到忽视。

许多人热衷于重复地造轮子，认为自己有效地解决了一些实际的问题，但是这些问题或许在很多年前已经被科学家们所解答。

现在，就让我们在本篇文章中一起回顾 Regular expression 背后的经典计算理论之一 —— 自动机理论 (Automata theory)

系列文章更新:

• Regular Expression 从理论到实践系列 - II 已经发布
• Regular Expression 从理论到实践系列 - III 已经发布
• Regular Expression 从理论到实践系列 - IV 已经发布

预先声明

本篇文章将无可避免地涉及到一些数学术语及符号，其中包括（但不限于）：

• 集合 (Set theory)
• 关系 (Relation)
• 图 (Graph)
• 定义 (Definition)，定理 (Theorem)，证明 (Proof)

请勿担心，我会尽可能地对涉及到的概念加以充分的说明和举例，以便于读者能够在不具备这些背景知识的情况下，也能够充分吸收和理解本文的内容。

同时，我也会尽可能地提供补充材料和引用，方便感兴趣的读者进行后续深入的阅读和学习。

术语和其翻译

计算机领域中大量的术语都属于舶来词汇，因此通俗易懂并且准确的翻译是非常重要的。可惜，要做到这一点非常地不容易。

对于本文中出现的术语，在中文翻译已经比较容易理解的情况下，我将直接使用中文翻译，并且视情况附带英文原文。在术语本身难以理解，并且中文翻译反而会导致理解困难的情况下，我将直接使用英文原文。

本篇文章将尽可能地保证内容的准确性和正确性，如有勘误或者改善意见，欢迎在评论区留言，或者通过主页顶部提供的社交方式来联系我。

背景知识：自动机（Automata), 可计算性 (Computability) 以及复杂度 (Complexity)

在 20 世纪 30 年代，计算理论 (Theory of Computation) 开始蓬勃发展，其主要分为三个分支，也就是上方标题中提到的：自动机，可计算性，复杂度¹。

这个三个分支都围绕着一个核心的问题：

什么是计算机最根本的计算能力，以及它的边界在哪？

自动机 (Automata)

自动机理论研究的是计算本身 (Computation) 的属性和相关的数学模型。这些模型在许多计算机科学的应用领域都有着举足轻重的地位。

其中一个模型，也就是本篇文章主要探讨的模型 —— 有限自动机 (finite automata) 应用于文字处理，编译器等领域。

另外一个模型，或许我将来也会写一篇对应的 Blog —— 上下文无关文法 (context-free grammar) 应用于编程语言以及人工智能领域。

因为可计算性和复杂度的研究都必须基于 一个精准的定义 —— 计算机(computer) 之上，而自动机理论让我们可以跳出计算机其他不相干的领域，来专注于研究计算本身。

只有这个分支是本系列文章的重点！

可计算性 (Computability)

在 20 世纪的前半叶，Alan Turing, Kurt Gödel, Alonzo Church 等人发现了某些基本问题是无法用计算机解决的。

其中一个问题是：比如提供一段程序代码文本，让计算机决定，该段代码是否最终会停止运行 —— 这就是大名鼎鼎的停机问题

对这个领域的研究，实际上为构造物理意义上的计算机有着指导作用 —— 比如现在我们所用的个人计算机大多是基于 register machine 模型来构造的。

复杂度 (Complexity)

计算机能够解决的问题，本质上有着不同的区分：有些问题天然易解决，而有些问题则是天然困难的。

研究者们在不断地探索中发现了一个非常优雅的模型基于问题的难度来划分和归类问题，这个发现是该领域最重要的成就之一。

有了这样一个模型，我们在面对这些问题的时候便有了更多的选择：

1. 理解问题难度的根源 —— 或许稍稍修改一下要解决的问题，我们就能得到一个更易于解决的问题
2. 放弃完美的解决方案 —— 在从理论上证实了问题的难度，我们可以不必再大费周折去寻找所谓 “更完美” 的解决方案
3. 有些问题只在一些极端情况下非常困难，而在大多数时候都比较容易解决 —— 我们可以在设计通用的解决方案时找到一个平衡

一个应用复杂度理论最经典的领域就是密码学

“如何设计一个更安全的算法？” 这个问题便可以转换成 “如何设计一个天然的计算难度非常之高的算法？“，这样我们设计出的来算法才能保障我们的密码不被轻易地破解。

有限自动机 (Finite Automata)

在上文中，我们提到了计算理论所关注的核心问题，但这个问题背后还有一个更加本质的问题 —— 什么是计算机 (computer)?

现实世界中的计算机构造过于复杂，为了简化和更方便的研究计算的本质，我们需要一个抽象的计算模型 (computational model) 来方便我们研究其性质。

计算模型可以有很多选择，取决于我们想要专注的问题。而对于本文要探讨的问题，我们只需要使用一个非常简单的模型 —— 有限状态机/有限自动机 (finite state machine / finite automaton)

有限状态机代表的是有限的状态，或者说有限的能够记忆当前机器运行状态的计算模型，这就是有限 (finite) 的含义。

文中提到的有限状态机和有限自动机在不专门说明的情况下，可以理解为同义词。 实际上自动机（Automata) 是一个更大的分类。

自动机 Automaton (复数: Automata) 一词来源于希腊语 αὐτόματο，意思是 “自我行动的”。一个自动机是一种抽象的自我推动的计算设备/模型，它的计算过程遵循预设好的操作序列。

那么，我们能用这样一个简单的计算模型（或者说计算设备）来做什么事情呢？答案是：很多！

现在让我们来看看一个极度简化的饮料自动贩卖机，这个贩卖机有以下几个特点：

1. 只接受 5 角和 1 元的硬币 (为了方便起见，后续将称 5 角为 0.5 元)
2. 该自动贩卖机只贩卖 1.5 元的饮料
3. 该自动贩卖机不设找零

那么我们应该如何设计这样一个自动售卖机呢？—— 我们需要 “记住” 当前收到硬币的总值，以及确定接下来收到新的硬币时，这个状态所发生的变化。

我们可以用这样一个状态图来表达我们的计算模型：

如上图所示，这个贩卖机一共有 4 个状态：0￥, 0.5￥, 1￥, 和 1.5￥，分别表示当前收到硬币的总值。这个贩卖机的状态会依据所接受的 输入(input) 而发生状态的迁移，这点我们可以通过观察图中的箭头以及箭头上的标签来得知。

当它处于状态 0￥ 时，接受 1￥ 的输入时，状态会变为 1￥，而接受 0.5￥ 时，状态则会变为 0.5￥，其他的状态迁移可以以此类推。

图中有两个特别的地方，一个是状态 0￥ 只有一个指向它的没有标签的箭头，这个符号代表这个状态为起始状态 (start state)。另外一个地方是状态 1.5￥ 是由一个双圆来表示的，这个符号代表这个状态为 接受状态 (accept state)。

细心的朋友可能会观察到：在到达状态 1.5￥ 时，提供更多的输入只会留在这个状态呢，这好像和我们对现实世界的认知太不符合。这是因为对于我们这个极度抽象和简单的计算模型来说，只需要到达状态 1.5￥，就足够说明单次计算已经成功了（这也不违反我们上面所提出的关于贩卖机的第三点要求）。

注意：自动机这样的计算模型常常会屏蔽现实世界中的很多细节，只留下表达计算本身的核心内容，这样更方便我们研究计算本身的性质，而非拘泥于无关紧要的细节。

一般来说，自动机的状态图会更加地 抽象，避免加入一些无关的符号，比如上图中的 ￥，同时也避免和特定的应用场景绑定。因此接下来，我们将更多地见到类似如下的状态图：

上图展示了一个的自动机，我们将它命名为 $M_1$, 它一共有 3 个状态：$q_1$, $q_2$, $q_3$。 $q_1$ 是 起始状态 (start state)，由一个单独指向它的空箭头表示。$q_2$ 是 接受状态 (accept state)，由一个双圆来表示。

$q_3$ 则是一个普通的状态。从一个状态指向另一个状态的箭头，称之为 状态转移 (transition)。

这个自动机收到由 0 和 1 组成的 字符串 (String)，比如说 1101，然后处理这个字符串，并且产生一个 输出 (output)。输出只能是 接受 (accept) 或者 拒绝 (reject) 其中之一。对于我们现在要探讨的计算问题，只提供一个 是/否 类型的答案就足够了，接下来我们还会看到其他的例子。

自动机每次只会从左到右一次读取输入字符的一个字符，每次读取一个字符之后，自动机就会根据预设发生状态迁移，当自动机读取完最后一个字符时，就会产生输出（再次强调：输出只能是接受或者拒绝）。当最后的状态是 接受状态 (accept state)，那么输出就是接受，否则为拒绝。

让我们来考虑下自动机处理字符串 1101 的具体流程：

1. 自动机开始，处于状态 $q_1$
2. 读取字符 1，发生状态转移 $q_1$ -> $q_2$
3. 读取字符 1，发生状态转移 $q_2$ -> $q_2$
4. 读取字符 0，发生状态转移 $q_2$ -> $q_3$
5. 读取字符 1，发生状态转移 $q_3$ -> $q_2$
6. 输出结果为：接受 (accept)，因为自动机最后处于接受状态 $q_2$

我们可以用其他不同的字符串来测试这个自动机，比如 11， 0100， 1010 等等。仔细观察可以发现，所有以 1 结尾的字符串都能够被这个自动机接受。

留给读者思考：除此之外，这个自动机还能接受其他类型的字符串吗？

有了自动机之后，我们多了以下可以考虑的问题：

• 如何正式地定义自动机（不借助图表）？
• 我们如何定义自动机所能接受的所有字符串（称之为语言 (language)）？
• 不同的自动机之间有没有联系，他们能互相关联起来吗？

Excursus: 字符串 (String) 和语言 (Language)

在我们回答上述问题以及给出正式的定义之前，我们需要定义一下上文提到的字符串 (String) 和语言 (Language)

字符串由字符（有时候也称之为字母）组成，我们定义字母表（alphabet) 为一个非空的有限集合（nonempty finite set），集合的成员是字母表中的符号（symbol），通常我们用希腊字母 $\varSigma$ (读作 sigma) 来表示字母表。

以下是常见的一些字母表的例子：

我们定义字母表上的字符串 (string over an alphabet) 为一个由字母表中的符号组成的有限序列，比如 $0010$ 是 $\varSigma_1 = \{0, 1\}$ 上的一个字符串，$abba$ 是 $\varSigma_1 = \{a, b\}$ 上的一个字符串 …

如果 $w$ 是字母表 $\varSigma_1$ 上的一个字符串，它的长度 (length) $|w|$ 定义为它所包含的符号的数量，比如 $w = 0010, |w| = 4$。

如果 $w$ 的长度为 0，那么我们称其为空串 (empty string), 写作 $\epsilon$ (读作 epsilon)。

如果有一个长度为 $m$ 的字符串 $x = x_1x_2...x_m, x_i \in \varSigma$ 和一个长度为 $n$ 的字符串 $y = y_1y_2...y_n, y_i \in \varSigma$, 这两个字符串都是在同个字母表之上定义的，那么字符串的拼接 (concatenation) 定义如下：

简而言之就是将 $x$ 和 $y$ 首尾相连组成一个新的字符串，通常可以省略中间的 $\circ$ 符号，直接写作 $xy$。如果拼接发生在一个同一个字符串上，并且连续拼接 $k$ 次，则可以简写为：

注意这里要和 $x$ 的 $k$ 次方区分开来。

字符串 $w$ 的反转 (reverse) 写作 $w^R$，通过将字符串中符号的顺序反转书写即可得到（比如：$|w| = n, w^R = w_nw_{n-1}...w_1$ )

语言 (language) 则是字符串的集合 (set of strings)，例如 $L_1 = \{ ab, abb, abab, bb \}$ 是字母表 $\varSigma = \{ a, b \}$ 上的一个语言。

有限自动机的正式定义 (Formal Definition of a finite Automaton)

通过上文中的例子，我们可以观察到，一个有限自动机具有5 个重要的要素

1. 所有的使用到的状态
2. 输入字母表
3. 关于状态转移的规则
4. 一个开始状态
5. 所有的接受状态

因此我们定义有限自动机为一个 5 元组 (5-tuple), 写作 $M = (Q, \varSigma, \delta, q_0, F)$²，其中：

• $Q$ 是有限的集合，叫做状态集
• $\varSigma$ 是有限的集合，叫做字母表
• $\delta: Q \times \varSigma \to Q$ 是状态转移函数 (读作 delta)
• $q_0 \in Q$ 是开始状态
• $F \subseteq Q$ 是有限的接受状态³的集合，它是 $Q$ 的一个子集

不要被状态转移函数的定义吓唬到了，其实非常好理解。如上文中所说的，假设自动机处于状态 $x$，读取一个字符 1，然后根据定义好的状态转移，进入下一个状态 $y$。

整个过程我们可以看作是一个状态转移函数的调用，它接受两个参数：当前状态以及读取的字符，然后输出一个新的状态，写作 $\delta(x, 1) = y$

正式的定义可以帮助我们精确地描述自动机的组成和行为。

现在让我们回顾一下上文提到的自动机 $M_1$:

拥有了正式的定义之后，我们还可以这样来描述 $M_1 = (Q, \varSigma, \delta, q_1, F)$:

• $Q = \{q_1, q_2, q_3 \}$
• $\varSigma = \{ 0, 1 \}$
• $\delta$ 则可以通过一个表格来描述：

  	$0$	$1$
  $q_1$	$q_1$	$q_2$
  $q_2$	$q_3$	$q_2$
  $q_3$	$q_2$	$q_2$

• $q_1$ 是起始状态
• $F = \{ q_2 \}$, 结束状态只有一个

如果 $A$ 是所有被自动机 $M_1$ 接受的字符串的集合, 那么我们就说集合 $A$ 是这个自动机 $M_1$ 的语言 (the language of machine $M_1$), 并写作 $L(M_1) = A$。

在这种情况下，我们可以称自动机 $M_1$ 识别 (recognizes) $A$⁴.

注意: 一个自动机可以接受 (accept) 多个不同的字符串，但是只能识别一个语言 (language) — 因为语言是字符串的集合

对于 $M_1$ 使:

那么则有 $L(M_1) = A$, 或者说 $M_1$ 识别 $A$。

Examples: 若干个具体的例子

例子 I

为了方便起见，我们首先命名这个自动机为 $M_2$。和上文提到的自动机不同的地方是，$M_2$ 的起始状态同时也是接受状态。这意味着 $M_2$ 也接受空串 $\epsilon$。

还记得之前关于状态转移函数的内容吗：$\delta$ 必须接受当前状态和读取的字符作为参数，当起始状态是接受状态时，自动机并没有读取任何字符，自动机就进入接受状态了，我们规定这种情况下：$M_2$ 也接受空串 $\epsilon$。

不难发现，这个自动机接受任何以 0 结尾的字符串，因此 $L(M_2) = \{ w \mid w = \epsilon \, \text{或者以 0 结尾} \}$

例子 II

假设我们要解决的问题是 —— 计算二进制数字中 0 的个数是否是偶数。那么我们可以构造以下自动机 $M_3$:

虽然自动机读取字符长度可能会非常长，但是为了解决这个问题，我们只需要用到两个状态即可。还记得我们最开头提到的内容吗？一个有限自动机只需要 记住 某些状态，然后利用这些状态就能完成及计算。

对于这个计数问题，自动机其实只需要记住：当前是否读取了偶数个 0 即可，因为正整数不是偶数就是奇数，自动机就还只需要另外来一个状态来表达奇数个 0 即可。之后我们只需根据下一个字符分别为 0 或者 1 的情况来确定我们的状态转移函数。

在这个例子中，空串 $\epsilon$ 的长度为 0，那么 0 的个数自然也为 0，而 0 又是偶数，所以我们需要接受空串 $\epsilon$

例子 III

接下来，让我们观察一个稍微复杂一点的例子，下图为自动机 $M_4$：

不难发现，这个自动机的字母表 (alphabet) 有些特殊: $\varSigma = \{<reset>, 0, 1, 2\}$。注意，$<reset>$ 本身是字母表中的一个符号，而并非字符串。对于我们的理论模型来说，这么做是完全没有问题的，你可以把 $<reset>$ 替换成 $3$ 也完全没有问题。

但是我们可以充分利用这个便利性，来增加自动机的可读性和语义性，方便我们研究它的性质。

仔细观察和思考之后不难看出，自动机 $M_4$ 持续地读取数字输入($0,1,2$)，然后计算他们的和 (sum)，如果当前的和是 $3$的倍数，则重置为起始状态。如果读取的下一个字符是 $<reset>$，也回到初始状态。

我们还可以这样来诠释：$q_0, q_1, q_2$ 状态分别代表数值输入的和对 3 进行模运算 (modulo 3) 的结果，自动机接受所有数值输入的和为 3 的倍数的字符串。

计算的正式定义 (Formal Definition of Computation)

上文中给出的自动机的例子，无一都是用自然语言来描述其计算过程。那么有没有办法更形式化地描述自动机的计算 (computation) 呢？—— 这就要借助数学符号了。

使 $M = (Q, \varSigma, \delta, q_0, F)$ 为有限自动机 (finite automaton)，使 $w = w_1w_2...w_n$ 为字符串，其中 $w_i \in \varSigma$。

那么自动机 $M$ 接受 (accept) 字符串 $w$，如果存在一个连续的状态序列 $r_0r_1...r_n$, 其中 $r_i \in Q$ 并满足以下 $3$ 个条件:

1. $r_0 = q_0$
2. 对 $i = 0,1,...,n-1$ 有 $\delta(r_i, w_{i+1}) = r_{i+1}$, 并且
3. $r_n \in F$

条件 1 确保自动机必须从起始状态开始计算。条件 2 确保计算过程根据定义好的状态转移 (transition) 从一个状态到另外一个状态。条件 3 确保自动机停止时处于接受状态。

我们说自动机 $M$ 识别 (recognizes) 语言 (language) A，如果 $A = \{ w \mid M \, \text{接受} 字符串 w\}$

让我们结合一下 $M_4$ 的例子来理解这个定义:

假设我们有输入字符串 $w = 10<reset>22<reset>012$, 那么 $M_4$ 根据定义接受字符串 $w$，因为存在以下连续的状态序列:

且满足条件 3: $q_0 \in \{q_0\}$, 因此 $M_4$ 的语言是：

正则语言 (Regular language⁵)

经过前文的详细说明和举例，希望读者至此已经大致理解了有限自动机的运作方式及其形式化的定义。现在，让我们来看看本篇文章最后一个定义：正则语言 (或者正规语言 - regular language)

一个语言被称为正则语言 (regular language)，当存在某个能识别 (recognizes) 该语言的 有限自动机 (finite automaton)。

回顾前文中的例子，我们可以确定：$L(M_1), L(M_2), L(M_3), L(M_4)$ 都是正则语言 (regular language)。

总结

本篇文章首先介绍了计算理论主要的三个分支，然后简单地介绍了字符串，字母表和语言以及他们的关系，紧接着给出了有限状态机 (finite automaton) 以及基于它的计算模型 (computational model) 的正式定义并列举了不少详细的例子，文章最后引入了正则语言。

本文所介绍的有限自动机都是确定的 (deterministic)，因此也称之为 DFA (deterministic finite automaton), 这一点我们将在后续的文章中更加详细地探讨。

后续文章预告

本系列的下一篇文章将会研究在正则语言上定义的操作 —— 如何通过这些操作将不同的正则语言联合在一起，并产生新的正则语言。同时引入另外一种有限自动机 —— 非确定有限状态自动机 (Nondeterministic finite automaton)，并研究它的特性。

想知道了解更多？请移步至下一篇文章：Regular Expression 从理论到实践系列 - II