有限状态自动机与正则语言

lalaouye · 2025-12-30 08:43:14 · 算法·理论

一些前言和前置

自动机分为很多种，不过我这里只讨论有限状态自动机。所以下文我们有时会直接用自动机指代有限状态自动机（FSM）。

首先具体解释自动机是干嘛用的，这里搬一下 oi-wiki，自动机是一种判断一个信号序列是否满足某种特定模式或规则的数学模型。

这里面的「信号序列」顾名思义就是一个按顺序排列的信号，比如说我们 OI 接触的字符串中从前往后的每一个字符，数列中从 1 到 n 每一个数，这些都可以理解成一个信号序列。

而「判断一个信号序列是否满足某种特定模式或规则」可以利用我们学过的一些自动机理解，我们可以利用 AC 自动机判断是否存在 S_i 是 T 的子串，这就是一种规则，也可以利用后缀自动机判断 T 是否是 S 的子串，这也是一种规则。

这里先简要介绍一些概念和符号。

令 \Sigma^* 表示非负整数个 \Sigma 中的字符组成的所有字符串。
语言是字符集 \Sigma 上的字符串的一个集合，也即 \Sigma^* 的一个子集。将其叫做语言其实想想就会发现挺有意思的。当然，所有的有向无环图也可以是一个语言，因为有向图与 01 串之间可以建立双射。

自动机与形式语言理论紧密关联，通过它独特的模型定义自动机识别的语言。这里似乎能够感受到自动机为啥要叫自动机，我的理解是只需要输入字符就可以自动判定以及定义集合（先知道就行，不要求现在就理解），不过我的理解是肤浅的。

自动机并不是算法，也不是数据结构，而是一种数学模型。同一个自动机可以有多种方式构建，哪些自动机是同一个自动机？比如说对于后缀自动机，我们可以用 trie 暴力压字符串的每个后缀，也可以直接建立 SAM，但是它们都是同一个自动机。具体的定义会在之后给出。

自动机的核心结构可以看作一个有向图，这里我们称它为 状态图。

确定性有限状态自动机（DFA）与非确定性有限状态自动机（NFA）

有限状态自动机分为两种，分别为确定性有限状态自动机（DFA），和非确定性有限状态自动机（NFA）。

我们学过并且常用的 AC 自动机，后缀自动机以及子序列自动机都是 DFA。DFA 的结构相对简单，它的确定性体现在它判定过程是确定的，即在一个状态顶点输入字符后对应的后继是唯一的。接下来严谨介绍一下它的结构由哪些部分组成。

DFA 可以刻画成一个五元组 (Q,\Sigma,\delta,q_0,F)，其内容为：

有限状态集合 Q。可以视为状态图上的顶点。
字符集 \Sigma。该自动机只能接受的字符。
转移函数 \delta:Q\times\Sigma\rightarrow Q，它是一个接受两个参数返回一个值的函数。第一个参数是状态，第二个参数是字符，返回的是一个状态。转移函数就相等于状态图上的边，每条边上都有一个字符，结合所学过的自动机不难理解。
起点 q_0。q_0\in Q，是输入字符串前默认的起点。
接受状态集合 F。F\subseteq Q，最终停止时用来判断信号序列是否满足条件，也即该 DFA 是否能够接受。

现在我们再回忆我们所学过的自动机，就会发现结构清晰了很多。

那么这个自动机具体又是怎么进行判断的呢？我们将求出输入串 w 在 DFA 中的状态序列，并判断它是否被接受的过程称作计算。

计算过程就是我们状态 r_0 从 q_0 开始，从前往后输入字符 w_i 并不断调用 r_i\leftarrow \delta(r_{i-1},w_i)，如果最终 r_n\in F，则称当前 DFA 接受（accepts） w，否则称当前 DFA 不接受 w。

对于一个自动机 M，它识别的语言 L(m) 就定义为 \{w\ |\ M\ \text{accepts}\ w\}。我们定义 正则语言 为能由某个 DFA 识别的语言。显然不是所有语言都能被 DFA 识别出来。

那么 NFA 的“非确定性”如何理解呢？其实它跟 DFA 的区别就在于转移函数。首先我们允许空字符 \varepsilon 作为第二个参数，并且，函数返回的是一个集合，即我们可以将状态转移到集合中的任意一个元素。

形式化一下，记 \mathcal{P}(Q) 表示 Q 的幂集，\Sigma_{\varepsilon} 表示 \Sigma\cup\{\varepsilon\}。对于转移函数 \delta:Q\times\Sigma_{\varepsilon}\rightarrow\mathcal{P}(Q)，接受两个参数，第一个是状态，第二个是字符，返回的是一个状态集合，注意，这里的状态集合可以为空。

对于 NFA 的计算，我们只需要满足存在一个合法的状态序列使得 r_n\in F 即可接受。

这个东西看起来要比 DFA 自由一些，那么 NFA 可不可以比 DFA 识别更多的语言呢？答案是否定的。事实上，我们可以证明 DFA 与 NFA 等价。我们称两个自动机等价，当且仅当它们识别的语言相同。于是，DFA 与 NFA 等价就说明，每个 NFA 都等价于某个 DFA，每个 DFA 都等价于某个 NFA。后者是显然的。对于前者，我们可以通过 幂集构造 将一个 NFA 转为一个 DFA。所以，NFA 识别的语言也是全体正则语言。

幂集构造其实很简单，我们将状态改造成“可能能到达的点的集合”，然后利用原先的 NFA 信息去连边建立 DFA 即可。

但是 NFA 并非毫无意义，它很多时候可以节省很多的状态数，比如说我们可能可以将状态数为 \mathcal{O}(2^n) 的 DFA 优化成等价的状态数为 \mathcal{O}(n) 的 NFA。

正则表达式

顾名思义，正则表达式就是一种描述正则语言的方法，也是理解正则语言的另一个视角，现在我们来定义正则表达式。

对于一个正则表达式 R，定义 L(R) 表示 R 对应的语言，正则表达式 R 可以是：

通过刚刚的文字描述我们会发现，我们的正则表达式与 FSM 是等价的，因为都代表了一个正则语言。每个正则表达式都可以通过 Thompson 构造法 转换为一个 NFA，每个 DFA 都可以通过 状态消除法 转换为一个正则表达式。通过这两种方法可以证明它们等价。

这里简述一下这两种方法，实际上在座的各位应该推一推也能会（。

首先 Thompson 构造法其实就是一个归纳构造的过程，事实上我们刚刚在给予正则表达式定义的时候就是一个归纳的过程。对于 (R_1+R_2) 操作，我们可以进行类似电路图的并联的构造，对于 (R_1R_2) 我们可以进行类似电路图的串联的构造，对于 (R^*)，我们只需要令其自动机的终止状态连向起始状态即可。你可能会纳闷自动机哪来的终止状态，我们在 NFA 中随便就可以构造出一个终止状态。

而状态消除法，本质上就是让状态数不断减少，每次找一个状态删除，它带来的影响我们可以改变其它状态之间的边刻画。

我们在这里定义 广义非确定性有限状态自动机（GNFA），它依旧可以刻画成一个五元组 (Q,\Sigma,\delta,q_s,q_t)。其中前两个意义跟上面的一样，q_s 是起始状态，q_t 是终止状态，而 \delta:(Q \setminus \{q_t\})\times(Q\setminus \set{q_s})\rightarrow \mathcal{R} 是转移函数，每条边上是一个正则表达式，其计算过程的定义如下：

若串 w 可以表示为 w_1w_2\cdots w_k\ (w_i\in\Sigma^*)，且存在状态序列 q_0,\cdots,q_k 使得

则称这个 GNFA 接受串 w。

我们这里定义它可以辅助我们完成证明。我们显然可以通过若干调整使得一个 DFA 转换为一个等价的 GNFA。

然后如果 GNFA 的状态数大于 2，我们找一个非终始状态，设其为 q_r，我们可以构造一个新的 GNFA (Q\setminus\set{q_r},\Sigma,\delta',q_s,q_t)，我们令 \delta'(q_i,q_j)=((\delta(q_i,q_r)(\delta(q_r,q_r)^*)\delta(q_r,q_j))+(\delta(q_i,q_j)))。考虑原本经过 q_r 的路径，我们通过这样的构造在边上进行了等效替代。

最后 \delta'(q_s,q_t) 就是得到的正则表达式。

它的一些封闭性就不讲了，因为我还不太会也还没有需要用到它的地方。对于它的代数定律是简单的，这里就不多阐述。讲这个主要是增加一种新的理解方式。

Myhill–Nerode 定理

这个定理我是真的喜欢，它可以更好的理解之前学过的自动机，说明了后缀自动机的状态数已经做到了最优，而且还可以用它草过一些题目！

首先该定义引入了一个概念：Nerode 等价关系。

它的内容是，对于一个语言 L 和任意串 x,y\in\Sigma^*，如果对于任意 z\in\Sigma^*，要么 xz 和 yz 同时属于 L，要么同时不属于 L，则称 x,y 关于 L 等价，记作 x\equiv_L y。

而 Myhill-Nerode 定理声称，一个语言 L 是正则的，当且仅当 \Sigma^* 通过等价关系 \equiv_L 划分成的等价类数量有限。我们把所有有限字符串集合划分成若干等价类。如果它们只有有限个时，我们可以利用这些等价类构造一个识别该语言的 DFA。而 DFA 的状态数就是等价类个数，我们同时可以说明，这个状态数是能识别该语言的 DFA 的状态数的下界。

这个定理是很容易感受的。我们可以利用等价关系构造能识别 L 的 DFA：

有限状态集合 Q。每个状态代表了一个等价类，我们可以随意选定一个代表元。
字符集 \Sigma。字符集显然。
转移函数 \delta。我们只需要将代表元后加入转移的字符，然后找到新字符串所在的等价类，函数返回值就是对应的状态。
初始状态 q_0。就是空串所在的等价类。
接受状态集合 F。就是属于 L 的那些等价类对应的状态。

我们发现，SAM 就是根据 endpos 等信息不断划分等价类构造出的 DFA。

对于这个定理在 OI 中的应用，它可以处理一些判定条件简单的字符串判定问题。很多地方的文章或题解对于该定理的用武之地似乎都是一笔带过，但是我认为这样说的可能有点太浅了，反正本蒟蒻感受了很久。下面有几道例题，我会结合第一个题以我的理解进行一定解释。

P12294 [THUPC 2025 决赛] 一个 01 串，n 次三目运算符，最后值为 1（加强版）

这道题定义了一个语言，该语言内的字符串满足能通过若干操作使得最后只剩下一个字符 1。

对于这个语言是否是正则语言，我没有非常直接的证明方式，虽然这个语言可以通过若干正则表达式表示出来，但是如果必须得不断运算直到无限次才能表示呢？我似乎不清楚这方面的定义，不过我们可以证明在本题中，我们的正则表达式迭代有限次后就不会再产生变化。

我们通过 R_{k,0} 表示至少包含所有长度 \le k 且可以变成 0 的字符串，R_{k,1} 表示所有长度 \le k 且可以变成 1 的字符串。我们可以通过它们的组合进行拓展至 k+2，实验表明存在一个时刻 R_{k,0}=R_{k+2,0},R_{k,1}=R_{k+2,1}。

所以我们希望找出一个自动机表示这个语言。通过观察这题的操作，我们操作规则比较简单，一段前缀对后面的影响有限，所以等价关系多，从而等价类不多，并且其内部长度最小的元素不大。我们划分等价类，本题中我们只需要考察所有 |S|\le 9 的字符串，并只需要往后加入 |z|\le 6 的字符串 check 就能将等价类划分出来，然后直接建立自动机即可。

不过这题还需要构造，我们采用分治结构，设 f(l,r,c) 表示是否能让 [l,r] 变成 c，这里需要我们建立能变成 01，10 等字符串的自动机，我们发现其状态数最大也只有 47，我们可以利用线段树快速维护区间在自动机的移动过程，再使用启发式合并的技巧即可做到 \mathcal{O}(n\log^2n+n|Q|)。

我们发现，我们通过该定理构造出了极小的自动机，而它之所以能这么用，主要源于它的操作规则简单，前缀影响有限，于是等价类个数自然比较少，于是我们就能做了。

一些例题

E - Median Replace 是元老级题目，不过结合了 dp 套 dp 的思想，不过并不难。

[JOIST 2024] 卡牌收集 / Card Collection 也是类似的，可以自己去感受。

还有一些其它自动机的应用，这里推荐一些题目（主要是 dp 套 dp）。

[ZJOI2019] 麻将。

[NOI2022] 移除石子。

CF506E。在不改变计数结果的前提优化状态数。

对于字符串的应用比较常见，这里就先不列了。

可能并没有结束。