有限状态自动机学习笔记

MZMTab · 2026-04-21 17:19:57 · 算法·理论

有限状态自动机

前言

有限状态自动机不属于字符串，但是和字符串关系很大。许多字符串算法本身就是自动机。虽然本文会大量运用到“字符集”“字符串”等概念，但并不是说明有限状态自动机只能用于字符串。在编译原理等领域有限状态自动机有重要作用。

本文是一个以理论为主的有限状态自动机入门。文章较长，难免有疏漏，欢迎指出。

有限状态自动机（Finite State Machine,FSM，下文也简写为自动机），是一类比较简单的计算模型。

在本文中，记 \Sigma^\ast 为由仅由属于 \Sigma 的字符拼接而成的字符串的集合。特别地，规定空字符串 \varepsilon \in \Sigma^\ast。显然 \Sigma ^ \ast 的集合大小无限。需要注意，对于自动机的讨论，离开了字符集 \Sigma 是没有意义的。由于 DFA 的定义中需要向字符集中所有的点都有出边，为避免图过于复杂，举例时一般令 \Sigma=\{0,1\}。

:::info[AIGC 使用声明]{open}

部分状态图由于过于繁琐（状态数超过 10 个）由 AI 生成，减少重复的工作，且经过人工核验，并在相应位置标出。

:::

由于洛谷专栏不支持 Graphviz dot 渲染状态图，会以 dot 源码形式出现，故推荐在博客园阅读。

:::info[仍然想在洛谷专栏查看]

使用篡改猴，新建一段这样的脚本刷新页面即可。（安装篡改猴可以参考这篇文章：油猴插件安装指北 ）

// ==UserScript==
// @name         Replace Dot Code By Graphviz SVG
// @namespace    http://tampermonkey.net/
// @version      2026-04-24
// @description  Replace Dot Code By Graphviz SVG for my artical
// @author       MZMTab
// @match        https://www.luogu.com.cn/article/rodk5xtv
// @require      https://cdn.jsdelivr.net/npm/@viz-js/[email protected]/lib/viz-standalone.js#sha384=c7kxrKbTexPod010RmdUIPNyuhsAkX+hFl1nr5cz2IFWH4rWiap8u8XCiM545i/T
// @grant        none
// ==/UserScript==

(function() {
  'use strict';
  const observer = new MutationObserver((mutations) => {
    if (document.querySelector('.code-container')) {
      observer.disconnect();
      DrawGraphViz();
    }
  });
  // 开始监听整个文档变化
  observer.observe(document.body, {
    childList: true,
    subtree: true
  });
  function DrawGraphViz() {
    const dotBlocks = document.querySelectorAll('pre code.language-dot');
    console.log('dotBlocks length:', dotBlocks.length); // 打印长度
    dotBlocks.forEach(block => {
      const dotCode = block.textContent;
      const container = document.createElement('div');
      container.className = 'graphviz-container';
      block.parentNode.replaceWith(container); // 替换原代码块为容器

      Viz.instance().then(viz => {
        try {
          const svg = viz.renderSVGElement(dotCode);
          container.appendChild(svg);
        } catch (error) {
          container.innerHTML = `<div style="color:red">Graphviz错误: ${error.message}</div>`;
        }
      });
    });
   } // ...处理dotBlocks的代码
})();

:::

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

OI 中多数自动机都是 DFA。

确定性有限状态自动机（Deterministic Finite Automaton,DFA）定义为一个五元组 (Q,\Sigma,\delta,q_0,F)，其中

对于一个字符串 w \in \Sigma ^ \ast,|w|=n 和 DFA M=(Q,\Sigma,\delta,q_0,F)，若存在一个状态序列 r_0,r_1,\dots,r_{n} 满足

则称 M 接受 w（或 M \text{ accepts } w）。

由于 DFA 每步转移都是确定的，上述的状态序列 r_0,r_1,\dots,r_n 对于 \Sigma^\ast 上任意字符串都是唯一确定的。

定义形式语言（简称语言）为 \Sigma ^ \ast 的一个子集（大小可以为无限）。

自动机 M 能识别的语言定义为 \{w \mid M \text { accepts } w\}，记为 L(M)。

定义正则语言为能够被某个 DFA 识别的语言。

为了方便说明，我们将求出输入串 w 在 DFA 中的状态序列，并判断其是否被接受的过程称为计算。显然，在一个已经建好的 DFA 上计算一个长为 n 的字符串的时间复杂度为 \Theta(n)。

:::info[不能被任一 DFA 识别的语言]

有两个经典的例子。

这两个例子都需要一个无限的状态集合，不满足“有限”。

:::

值得指出的是任意有限大小的语言均为正则语言，Trie 树就是识别它们的 DFA。

可以直观地用状态图描述一个 DFA。在本文中，状态图中红色的结点表示起点，即 q_0，双圈表示接受状态集合中的点。

如一个简单的 DFA 求一个 01 串的 1 的数量是否为奇数（__builtin_parity）的状态图如下

digraph DFA{
  rankdir=LR;
  node [shape=circle];
  0 [color=red];
  1 [shape=doublecircle];
  0 -> 1 [label="1"];
  0 -> 0 [label="0"];
  1 -> 0 [label="1"];
  1 -> 1 [label="0"];
}

该 DFA 为

对于串 \texttt{01101}，其状态序列为 0,0,1,0,0,1;1\in F，故该自动机接受该串。

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

非确定性有限状态自动机（Nondeterministic Finite Automaton，NFA）是 DFA 的自然拓展。每个点通过某个字符可能有多个后继，且允许由空字符串转移（严谨地这应该叫 ε-NFA，本文与 OI-wiki 和徐哲安论文保持一致。）。令 \mathcal{P}(Q) 为 Q 的所有幂集（所有子集的集合），\Sigma_{\varepsilon}=\Sigma \cup \{\varepsilon\}。

非确定性有限状态自动机（Nondeterministic Finite Automaton,NFA）定义为一个五元组 (Q,\Sigma,\delta,q_0,F)，其中

对于一个字符串 w \in \Sigma ^ \ast,|w|=n 和 M=(Q,\Sigma,\delta,q_0,F)，若存在一个状态序列 r_0,r_1,\dots,r_{n} 满足

则称 M 接受 w（m\text{ accepts }w）。

NFA 的计算的定义是类似的。在 NFA 上计算一个长度为 n 的串的复杂度为 \mathcal O{(ns^2)},s=|Q|。这是由于在 NFA 的计算过程中，最坏包含 s 中可能的后继状态（|\delta(i,c)|），每个后继的到的状态数最坏为 s 个。

Trival 地使用 bitset 优化可以做到 \mathcal O (\frac{ns^2}{w})。

使用四毛子（Method of Four Russians）优化可以做到 \mathcal O(\frac{ns^2}{w \log n})，受限于篇幅，暂且不表。

DFA 与 NFA 的等价性

显然所有的 DFA 都是一个 NFA。（严谨地说需要一点小变化，将转移函数修改为单元素集合即可）那么 NFA 是否能识别更多的语言？

答案为否。任何一个 NFA 都与某个 DFA 等价。

先定义一下两个 FSM 等价：若两个 FSM 等价，当且仅当它们可以识别相同的语言，即 M,N 等价当且仅当 L(M)=L(N)。

现在我们要做的是对于任意一个 NFA N=(Q,\Sigma,\delta,q_0,F) 构造一个 DFA M=(Q^\prime,\Sigma,\delta^\prime,q_0^\prime,F^\prime) 与之等价。该构造被称为幂集构造。如下：

令 E(q),q\in Q 为 N 上 q 状态仅通过 \varepsilon 能到达的集合（包含 q 本身，可称为 ε-闭包）。

比如这样的一个简单的 NFA 实现匹配任意个数的 0，\Sigma=\{0,1\}：

digraph NFA1{
  rankdir=LR;
  node[shape=circle];
  q0 [color=red];
  q1[shape=doublecircle];
  q0 -> q1 [label="ε"];
  q1 -> q0 [label="0"];
}

则 E(q_0)=\{q_0,q_1\},E(q_1)=\{q_1\}。

在绘图时，为了方便，用 00 表示 \varnothing，01 表示 \{q_0\}，依次类推。

digraph DFA2{
  rankdir=LR;
  node[shape=circle];
  00;01;
  10[shape=doublecircle];
  11[color=red,shape=doublecircle];
  11 -> 11 [label="0"];
  11 -> 00 [label="1"];
  01 -> 00 [label="1"];
  01 -> 00 [label="0"];
  00 -> 00 [label="1"];
  00 -> 00 [label="0"];
  10 -> 00 [label="1"];
  10 -> 00 [label="0"];
}

然后注意到 10 和 01 状态时没有意义的，直接删掉即可（相当于后文提到的 DFA 最小化）。

digraph DFA3{
  rankdir=LR;
  node[shape=circle];
  00;
  11[color=red,shape=doublecircle];
  11 -> 11 [label="0"];
  11 -> 00 [label="1"];
  00 -> 00 [label="1"];
  00 -> 00 [label="0"];
}

显然这个 DFA 和原来的 NFA 时完全等价的。

正则表达式与正则语言

:::warning[注意]{open}

本处所说的正则表达式与 C++ 的 regex 头文件，python 的 re 库所实现的并不相同。

:::

正则表达式的定义

定义正则表达式 R，称 L(R) 为 R 对应的语言。在理解上（非严谨定义），可以将正则表达式视为一种规则，其对应的语言即满足该规则的所有的字符串的集合。

正则表达式由公理化定义定义：

正则表达式与 FSM 满足等价关系。即所有正则表达式只能对应正则语言，任一正则语言均可由某个正则表达式对应。下面两节即为正则表达式与 FSM 相互转化的构造。

Thompson 构造法

我们由正则表达式 L 来构造 NFA。

digraph LNFA1{
  rankdir=LR;
  node [shape=circle];
  q0 [color=red];
  q1 [shape=doublecircle];
  q0 -> q1 [label="c"];
}

digraph LNFA2{
  node [shape=circle];
  q0 [color=red];
  q1 [shape=doublecircle];
}

digraph LNFA3{
  rankdir=LR;
  node [shape=circle];
  q0 [color=red];
  q1 [shape=doublecircle];
  q0 -> q1 [label="ε"];
}

以上三种构造均满足 |F|=1，后面可以直接将起点、终点接到 NFA 中。

digraph LNFA4{
  rankdir=LR;
  node[shape=circle];
  q0 [color=red];
  qt [shape=doublecircle];
  subgraph cluster_R1 {
    label="R1的NFA";
    style=dotted;
    ql1;
    qr1[shape=doublecircle];
    ql1 -> qr1 [style="dashed"];
  }
  subgraph cluster_R2 {
    label="R2的NFA";
    style=dotted;
    ql2;
    qr2[shape=doublecircle];
    ql2 -> qr2 [style="dashed"];
  }
  q0 -> ql1 [label="ε"];
  qr1 -> ql2 [label="ε"];
  qr2 -> qt [label="ε"];
}

digraph LNFA5{
  rankdir=LR;
  node[shape=circle];
  subgraph cluster_R1 {
    label="R1的NFA";
    style=dotted;
    ql1;
    qr1[shape=doublecircle];
    ql1 -> qr1 [style="dashed"];
  }
  subgraph cluster_R2 {
    label="R2的NFA";
    style=dotted;
    ql2;
    qr2[shape=doublecircle];
    ql2 -> qr2 [style="dashed"];
  }
  q0 [color=red];
  qt [shape=doublecircle];
  q0 -> ql1 [label="ε"];
  q0 -> ql2 [label="ε"];
  qr1 -> qt [label="ε"];
  qr2 -> qt [label="ε"];
}

digraph LNFA6{
  rankdir=LR;
  node[shape=circle];
  q0 [color=red];
  qt [shape=doublecircle];
  subgraph cluster_R {
    label="R的NFA";
    style=dotted;
    ql;
    qr[shape=doublecircle];
    ql -> qr [style="dashed"];
  }
  q0 -> ql [label="ε"];
  qr -> qt [label="ε"];
  qr -> ql [label="ε"];
}

其中的虚线省略了自动机的具体结构。

具体的例子见下一节。

DFA 转正则表达式

我们引入一种新的 FSM：广义非确定性有限状态自动机（Generalized Nondeterministic Finite Automaton, GNFA），说白点就是将 NFA 中所有的边换成正则表达式，且有且只有一个接受状态的自动机。

严格定义：

广义非确定性有限状态自动机依然是一个五元组 (Q,\Sigma,\delta,q_s,q_t)，其中

对于一个字符串 w \in \Sigma ^ \ast,w=w_1w_2\dots w_n,w_i \in {\color{red} \Sigma ^\ast} 和 GNFA M=(Q,\Sigma,\delta,q_s,q_t)，若存在一个状态序列 r_0,r_1,\dots,r_{n} 满足

则称 M 接受 w（或 M \text{ accepts } w）。

然后我们将 DFA 转成 GNFA。

设原来的 DFA 为 M=(Q,\Sigma,\delta,q_0,F)。

增设一个超级源点和超级汇点（q_s,q_t 且 q_s,q_t \not \in Q）。从 q_s 向 q_0 连 \varepsilon 的转移，从 F 中所有元素向 q_t 中连 \varepsilon 的转移，合并重边并补全所有未描述的点对之间的 \varnothing 转移。

然后我们尝试缩小这个 GNFA。

若删除 q_r，且 q_r \neq q_s,q_r\neq q_t。

需要枚举所有的转移 q_i \to q_j。

即可删除 q_r。像这样不断进行下去直到只剩下 q_s 和 q_t 两个点，它们之间的正则表达式记为答案。

还是以这个 DFA 为例：

digraph DFA1{
  rankdir=LR;
  node [shape=circle];
  0 [color=red];
  1 [shape=doublecircle];
  0 -> 1 [label="1"];
  0 -> 0 [label="0"];
  1 -> 0 [label="1"];
  1 -> 1 [label="0"];
}

新增源汇并补全原来没有的边，转化为 GNFA：

digraph GNFA1{
  rankdir=LR;
  node [shape=circle];
  qs[color=red];
  qt [shape=doublecircle];
  0 ;
  1 ;
  qs-> 1 [label="∅"];
  qs-> 0 [label="ε"];
  qs-> qt[label="∅"] 
  0 -> 1 [label="1"];
  0 -> 0 [label="0"];
  1 -> 0 [label="1"];
  1 -> 1 [label="0"];
  1 -> qt[label="ε"];
  0 -> qt[label="∅"];
}

删除结点 0。并化简结果。

digraph GNFA2{
  rankdir=LR;
  node [shape=circle];
  qs[color=red];
  qt [shape=doublecircle];
  1 ;
  qs-> qt[label="∅"];
  qs-> 1 [label="0*1"];
  1 -> 1 [label="0+10*1"];
  1 -> qt[label="ε"];
}

删除结点 1。（正则表达式太长了，记为 L，直接提出来）

这个正则表达式怎么意思呢？开头若干个 0，然后有一个 1，之后分为若干字段，每段要么存在两个 1，要么全是 0。这正是我们想要的正则表达式！

笔者将其改写成真实在 VS code 搜索框能用的正则表达式 0*1(0|(10*1))*，实验完全正确的（前后加 \n 是为了只匹配一行，不会只匹配一个子串）。

而我们尝试将 L = 0^\ast 1(0+10^\ast 1)^\ast 这个正则表达式重新建成 FSM。（严格按照 Thompson 构造有 17 个状态，太多了，做了一些简化，比如连续的 \varepsilon 可以丢掉）

digraph LtoNFA{
  rankdir=LR;
  node [shape=circle];
  qs [color=red];
  qt [shape=doublecircle];
  qt -> 2[label="ε"];
  qs -> 1 [label="0"];
  1 -> qs [label="ε"];
  1 -> 2 [label="1"];
  2 -> qt[label="0"];
  2 -> 3[label="1"];
  3 -> 4[label="0"];
  4 -> 3[label="ε"];
  4 -> qt[label="1"];
}

看样子似乎不大能继续化简，但是由之后的内容可以继续化简这个自动机。这个例子可以说明，Thompson 构造法只完成了合法的构造，并没有进行最小化。

:::info[严格遵循 Thompson 构造法完整的 NFA 的 graphviz dot 源码]

太长了。所以只把 dot 源码放出来。渲染结果。AI 生成，人工检验过。

digraph NFA {
  rankdir=LR;
  node[shape=circle];
  s_a [label="s_a", color=red];
  f_h [label="f_h", shape=doublecircle];

  // 0* 部分
  s_a -> q0 [label="ε"];
  s_a -> f_a [label="ε"];
  q0 -> q1 [label="0"];
  q1 -> q0 [label="ε"];
  q1 -> f_a [label="ε"];

  // 1 部分
  f_a -> s_b [label="ε"];
  s_b -> f_b [label="1"];

  // (0|10*1)* 部分
  f_b -> s_h [label="ε"];
  s_h -> s_g [label="ε"];
  s_h -> f_h [label="ε"];

  // 0|10*1 的并集
  s_g -> s_f [label="ε"];  // 分支: 0
  s_g -> s_c [label="ε"];  // 分支: 10*1
  s_f -> f_f [label="0"];
  f_f -> f_g [label="ε"];
  s_c -> f_c [label="1"];
  f_c -> s_d [label="ε"];  // 链接 0*
  s_d -> d0 [label="ε"];
  s_d -> f_d [label="ε"];
  d0 -> d1 [label="0"];
  d1 -> d0 [label="ε"];
  d1 -> f_d [label="ε"];
  f_d -> s_e [label="ε"];  // 链接第二个 1
  s_e -> f_e [label="1"];
  f_e -> f_g [label="ε"];  // 合并分支接受

  // 闭包循环
  f_g -> s_g [label="ε"];
  f_g -> f_h [label="ε"];
}

:::

上面那个例子没有合并重边这一步。我再随手画个 DFA。

digraph DFA4{
  rankdir=LR;
  node[shape=circle];
  0 [color=red];
  1 [shape=doublecircle];
  0 -> 1 [label="0"];
  0 -> 2 [label="1"];
  1 -> 2 [label="0"];
  1 -> 2 [label="1"];
  2 -> 2 [label="0"];
  2 -> 2 [label="1"];
}

补出源汇、合并重边得到下图。（省略转移为 \varnothing 的边）

digraph GNFA3{
  rankdir=LR;
  node[shape=circle];
  qs [color="red"];
  qt [shape=doublecircle];
  qs-> 0 [label="ε"];
  0 -> 1 [label="0"];
  0 -> 2 [label="1"];
  1 -> 2 [label="0+1"];
  1 -> qt[label="ε"];
  2 -> 2 [label="0+1"];
}

然后就可以得到正则表达式为 0。

正则表达式的代数性质

可能需要一点简单的抽象代数基础，如有不熟悉的地方请自行百度。

并运算（R_1R_2）满足交换律、结合律、幂等性，单位元为 \varnothing。

连接运算（R_1+R_2）满足结合律，单位元为 \varepsilon，零元为 \varnothing。

并（相当于 \times）和连接（相当于 +）满足分配律：L(M+N)=LM+LN。

Kleene 星号满足 (L^\ast)^\ast=L^\ast,\varnothing ^\ast=\varepsilon,\varepsilon^\ast=\varepsilon。

这几个性质都比较显然，证明略。

正则语言的封闭性

显然，对于正则表达式的代数性质可以直接推广到正则语言。本节正则语言通过运算后仍然是正则语言。由于上文已经说明 FSM 和正则表达式是完全等价的，所以以下在说明时只用 NFA、DFA、正则表达式中最方便的一种。

显然的是正则语言的并、连接、Kleene 星号结果均为正则语言，可以由 Thompson 构造法直接得到 FSM。

正则语言的补（\Sigma ^\ast \setminus L）是正则语言。可以交换 DFA 中的 F 和 Q \setminus F。

正则语言的交（L_1 \cap L_2）是正则语言。这个构造是 DFA (Q_1\times Q_2,\Sigma,\delta((q_1,q_2),c) = (\delta _1 (q_1,c) ,\delta _2(q_2,c ) ) , ({q_0}_1,{q_0}_2), F_1 \times F_2 )，其中的两集合的乘法表示笛卡尔积，即 S\times T = \{(s,t) \mid s\in S,t\in T \}。

正则语言的差（L_1 \setminus L_2）是正则语言。由 L_1 \setminus L_2 = L_1 \cap (\Sigma ^ \ast \setminus L_2) 可得。

正则语言的反转（L^R=\{s_n\dots s_2s_1 \mid s_1s_2\dots s_n \in L\}）是正则语言。正则表达式所有连接操作交换前后即可。

定义 h 为 \Sigma \to \Sigma ^\ast 的映射。则 s=s_1s_2\dots s_n 的同态 h(s)=h(s_1)h(s_2)\dots h(s_n)。正则语言的同态（H(L)=\{h(s) \mid s\in L\}）是正则语言。将 c \in \Sigma 的转移边边权全部换成 h(c) 的 DFA（显然存在一条链的构造）即可。

正则语言的逆同态（H(L)^{-1}=\{s \in \Sigma ^\ast \mid h(s)\in L\}）是正则语言。上述的逆过程。

Myhill-Nerode 定理

Myhill-Nerode 定理给出了判断一个语言是否为正则语言的方法。

对于语言 L 和字符串 x,y\in\Sigma^\ast，称 x 与 y 关于 L 等价（记为 x \equiv _L y）当且仅当 \forall z \in \Sigma ^\ast，xz \in L 和 yz \in L 同时成立或同时不成立（可以成为 Nerode 等价）。

如果学过 Trie 树很好理解这是在干什么。举个例子：对于正则表达式 L=(0+1)^\ast 01 构成的语言，即以 01 结尾的 01 序列，x=\texttt{10} 和 y=\texttt{0} 是关于 L 等价的，因为当 z \in 1+(0+1)^\ast 10 时 xz 和 yz 同时属于 L 而其它情况同时不属于 L。

不难验证 \equiv_L 的自反性、对称性与传递性，这个关系一个等价关系（equivalence relation）。故我们可以将 \Sigma ^ \ast 划分成若干个等价类。

现在可以提出 Myhill-Nerode 定理：一个语言 L 是正则的，当且仅当 \Sigma^\ast 通过 \equiv_L 划分出的等价类是有限的。

进一步，等价类数就是可以识别 L 的最小 DFA 状态数。这个最小的 DFA 在同构意义下（忽略标号）是唯一的。

这个定理的重要性在于已知等价关系就可以构造出 DFA。

具体地，假设 S_1,S_2,\dots,S_k 为由 \equiv_L 划分出来的 k 个等价类。[w],w\in \Sigma^\ast 表示 w 所在的等价类。

个人感觉这个定理很重要，故多举几个例子。

例子一：\Sigma=\{\texttt{a},\dots,\texttt{z}\},L=\{\texttt{a},\texttt{b}\}，显然为正则语言。划分出来的等价类有三个：空字符串、\{\texttt{a},\texttt{b}\}、其它所有情况（按习惯失配为状态 0）。（为了方便没有画出所有的边）

digraph MNHR0{
  rankdir=LR;
  node[shape=circle];
  1 [color=red];
  2 [shape=doublecircle];
  0 ;
  1 -> 2 [label="a"];
  1 -> 2 [label="b"];
  2 -> 0 [label="a 到 z"];
  1 -> 0 [label="c 到 z"];
  0 -> 0 [label="a 到 z"];
}

而直接对 L 建立 Trie 树的 DFA 并非最小，如下：

digraph TRIE0{
  rankdir=LR;
  node[shape=circle];
  1 [color=red];
  2 [shape=doublecircle];
  3 [shape=doublecircle];
  1 -> 2 [label="a"];
  1 -> 3 [label="b"];
  1 -> 0 [label="c 到 z"];
  2 -> 0 [label="a 到 z"];
  3 -> 0 [label="a 到 z"];
  0 -> 0 [label="a 到 z"];
}

例子二：\Sigma=\{0,1\},L=\{\varepsilon,\texttt{0000},\texttt{100}, \texttt{01}\}，显然为正则语言。划分出来的等价类如下

还有一个恒失配等价类为除上述状态之外的所有串，标号为 0。

digraph MHNR1{
  rankdir=LR;
  node[shape=circle];
  1 [color=red,shape=doublecircle];
  5[shape=doublecircle];
  1 -> 2 [label="0"];
  1 -> 3 [label="1"];
  2 -> 3 [label="0"];
  2 -> 5 [label="1"];
  3 -> 4 [label="0"];
  3 -> 0 [label="1"];
  4 -> 5 [label="0"];
  4 -> 0 [label="1"];
  5 -> 0 [label="0"];
  5 -> 0 [label="1"];
  0 -> 0 [label="0"];
  0 -> 0 [label="1"];
}

而建立 Trie 树需要 10 个结点（不要忘了失配状态）。

例子三：\Sigma=\{0,1\},L = \{000,0000,00000,\dots\}。即 L 为由超过 3 个 0 构成的全 0 串。

等价类划分（由正则表达式表示）为

DFA 建立如下：

digraph MHNR2{
  rankdir=LR;
  node[shape=circle];
  1 [color=red];
  4 [shape=doublecircle];
  1 -> 2 [label="0"];
  2 -> 3 [label="0"];
  3 -> 4 [label="0"];
  4 -> 4 [label="0"];
  1 -> 5 [label="1"];
  2 -> 5 [label="1"];
  3 -> 5 [label="1"];
  4 -> 5 [label="1"];
  5 -> 5 [label="0"];
  5 -> 5 [label="1"];
}

例子四：\Sigma=\{0,1\},L=\{0^n1^n \mid n \in \mathbb N\}。

等价类划分就发现存在无穷多个等价类，至少 [0^x]\neq [0^y],x \neq y,x,y \in \mathbb N。所以语言 L 不是正则语言。

例子五：\Sigma=\{\texttt{(},\texttt{)}\}，语言 L 为所有匹配的合法括号序列。

等价类划分为 S_k 为已有有 k 个未匹配的 (，且补全 k 个 ) 后为合法括号序列，和 F 表示已经非法的括号序列，有无穷多个等价类，故语言 L 不是正则语言。

DFA 最小化

虽然直接在 DFA 上判断是否接受某个串是 \Theta (n) 的，与 DFA 状态数无关，但是一些问题如 DP 套 DP 时复杂度常常与 DFA 状态数直接相关。而 NFA 的最小化是相当困难的，除非 P=PSPACE（伪多项式复杂度）。

以下讨论基于一个 DFA M=(Q,\Sigma,\delta, q_0,F)，且已经剔除了不可达状态（一遍搜索即可）。此部分令 n=|Q|。

状态的等价关系

定义 \hat \delta:Q \times \Sigma ^ \ast \to Q。

说白了 \hat \delta 定义了从 p 状态出发，通过字符串 w 转移得到的状态。

类似 Nerode 等价，我们定义 M 上两个状态 p,q \in Q 等价当且仅当 \forall w \in \Sigma ^ \ast，\hat\delta(p,w) \in F 和 \hat\delta(q,w)\in F 同时成立或同时不成立。记为 p \sim q。

不难发现 \sim 满足自反性、对称性、传递性，也是等价关系（equivalence relation）。我们可以将 Q 分为若干等价类，可以记为 G _1,G _2,\dots,G _k。我们仍然可以用 [q],q\in Q 表示 q 所在的等价类。

显然最小化的 DFA 每个等价类只有一个状态。而知道一个 DFA 的等价类划分后构建最小 DFA M^\prime 只需要遍历 i \to \delta(i,c),c \in \Sigma，在 M^\prime 中添加 \delta^\prime([i],c) \gets [\delta(i,c)]，F^\prime \gets\{[x] \mid x \in F\} 即可。这部分复杂度达到了理论下界 \Theta (n |\Sigma|)。

Moore 算法

并非 Boyer-Moore 算法，直接搜索很可能搜到 Boyer-Moore 算法。

这个思路比较直接，但同时效率略低。

初始划分为 \Pi=\{F,Q \setminus F\}。

不断细化 \Pi 直到 \Pi^\prime \neq \Pi。

每一轮迭代初始默认等价类集合为 \Pi，枚举每个等价类 G _i，枚举 G_i 中所有的状态 y，遍历出边得到一个状态数组 a,a_i = [\delta(y,i)],i \in \Sigma。

具体实现时需要设计一个哈希函数 H:\text{array of } |\Sigma| \text{ elements of } \Pi \to \mathbb N，可以使用类似 unordered_map<ull,vector<int>> 的实现。

放一个伪代码：

复杂度说明：每次进入第 2 行的 \textbf{while }\mathrm{True} 复杂度的均为 \mathcal O (n|\Sigma|)，而每次更新至少是一个元素分离，故总复杂度为 \mathcal O (n^2|\Sigma|)。

举个例子，假设我们需要最小化的 DFA 如下，为了方便令 \Sigma=\{a,b,c\}。

digraph TRIE3{
  rankdir=LR;
  node[shape=circle];
  1 [color=red];
  2 [shape=doublecircle];
  3 [shape=doublecircle];
  1 -> 2 [label="a"];
  1 -> 3 [label="b"];
  1 -> 0 [label="c"];
  2 -> 0 [label="a 到 c"];
  3 -> 0 [label="a 到 c"];
  0 -> 0 [label="a 到 c"];
}

初始化为 \Pi=\{\{0,1\},\{2,3\}\}。

• 第一次迭代，\Pi=\{\{0,1\},\{2,3\}\}，为了方便令 G_1=\{0,1\},G_2=\{2,3\}。初始 \Pi ^ \prime \gets \varnothing。

  • 枚举到 G=\{0,1\}。 哈希表中最后得到 \{(G_1,G_1,G_0):[1],(G_0,G_0,G_0):[0]\}，更新 \Pi ^ \prime \gets \{\{0\},\{1\}\}。
  • 枚举到 G=\{2,3\}。 哈希表中最后得到 \{(G_0,G_0,G_0):[2,3]\}，更新 \Pi ^ \prime \gets \{\{0\},\{1\},\{2,3\}\}。

• 第二轮迭代，\Pi = \{\{0\},\{1\},\{2,3\}\}。 初始 \Pi ^ \prime \gets \varnothing。

  • 枚举到 G = \{0\}，大小为 1，直接更新 \Pi ^\prime \gets \{\{0\}\}；
  • 枚举到 G = \{1\}，大小为 1，直接更新 \Pi ^\prime \gets \{\{0\},\{1\}\}；
  • 枚举到 G=\{2,3\}。 哈希表中最后得到 \{(G_0,G_0,G_0):[2,3]\}，更新 \Pi ^ \prime \gets \{\{0\},\{1\},\{2,3\}\}。

最终得到 \Pi=\{\{0\},\{1\},\{2,3\}\}。合并等价类得到 DFA 如下：

digraph MNHR0{
  rankdir=LR;
  node[shape=circle];
  1 [color=red];
  2 [shape=doublecircle];
  0 ;
  1 -> 2 [label="a"];
  1 -> 2 [label="b"];
  2 -> 0 [label="a 到 c"];
  1 -> 0 [label="c"];
  0 -> 0 [label="a 到 c"];
}

与上一章直接由 Myhill-Nerode 定理从语言构造相同。

值得一提的是，在随机生成的 DFA 上 Moore 算法迭代次数为 \mathcal O (\log n)，还算高效。

Hopcroft 算法

算法思想

该算法核心思想在于启发式分裂的思想，实现复杂度优化。

我们暂时先不考虑正确性，来看下算法的具体过程。

相较于 Moore 算法，十七行以前的，类似于 SPFA 对 Bellman-Ford 一样的队列优化。其正确性和复杂度的关键在于十七行以后的对工作队列 W 的更新。

:::info[关于工作队列]

在 Hopcroft 原论文中，实际上维护 |\Sigma| 个工作队列。但是可能后人发现只需要一个也可以保证正确性和复杂度，简化为了一个工作队列，比如 Knuutila 的论文中。

:::

而由这个高度概括的伪代码复杂度也很难看出，尤其是第七行和第九行的获取集合高度抽象，暂时无法确定具体的实现。

正确性证明

该算法流程等价于不断重复 Y 和 A 两集合和字符 c,c\in \Sigma，若 Y \cap A \neq \varnothing 且 Y \cap Q \setminus A \neq \varnothing，则 Y 显然应该被划分。我们称 A 为划分 Y 的证据。

工作队列 W 维护的实际上是还未使用的证据。当 A 作为证据划分了已有的等价类后，A 就失去了意义。

当 Y 被某个证据划分成 U,V 后，考虑如何更新 W。

• 考虑反证法证明。不妨假设存在一个集合 $Z$ 仅能由 $U$ 划分。那么必然存在 $a,b \in Z,\delta(a,c) \in U,\delta(b,c) \not \in U$。若 $\delta(b,c) \not \in Y$，则 $Y$ 可以作为划分 $Z$ 的证据，与 $Y\not \in W$ 矛盾；若 $\delta(b,c) \in V$，则 $V$ 亦可以做划分 $Z$ 的证据，与 $Z$ 仅能由 $U$ 划分矛盾。证毕！

高效的实现和复杂度

上述伪代码省略了大量的过程，与复杂度相关性比较大的是第九行获取需要划分的集合，以及 \Pi 和 W 用什么数据结构（广义的，数组也算数据结构）实现。

我们可以定义 \delta^{-1}:Q \times \Sigma \to \mathcal P(Q),\delta^{-1}(q,c)=\{u \in Q \mid \delta (u,c) =q\}。

这样就可以快速地找到 \mathrm{pre} 集合，进而能够快速的求得 \mathrm{divs}。

可以写出如下的 C++ 代码：

struct DFA{
    int n;//自动机状态数，标号 0 到 n-1
    int Sig;//自动机字符集大小，0 到 Sig-1
    vector<vector<int> > delta;//转移函数
    vector<int> acc;//是否接受
    int st;//起点
    DFA():n(0),Sig(0),st(0){}
    DFA(int _n,int _S,int _st):n(_n),Sig(_S),
        delta(n,vector<int>(_S,0)),
        acc(n,false),
        st(_st){}
    void print(){
        putchar('{');
        printf("%d,%d,",n,st);
        putchar('{');
        for(int i=0;i<n;i++){
            printf("{%d,%d}",delta[i][0],delta[i][1]);
            if(i==n-1){
                putchar('}');
            }
            putchar(',');
        }
        putchar('{');
        vector<int> accs;
        for(int i=0;i<n;i++){
            if(acc[i]){
                accs.push_back(i);
            }
        }
        for(int i=0;i<(int)accs.size();i++){
            printf("%d%c",accs[i],",}"[i==(int)accs.size()-1]);
        }
        putchar('}');
    }
};
DFA hopcroft(const DFA M){
    vector<vector<vector<int> > > deltaf(M.n,vector<vector<int>>(M.Sig,vector<int>()));
    vector<int> bel(M.n,0);
    for(int i=0;i<M.n;i++){
        for(int j=0;j<M.Sig;j++){
            int ed=M.delta[i][j]; 
            deltaf[ed][j].push_back(i);
        }
    }
    struct EqClass{
        vector<int> s;
        int cnt;
        EqClass():s(),cnt(0){}
        EqClass(vector<int> _s):s(_s),cnt(0){};
        void push_back(int y){s.push_back(y);}
        int size(){return (int)s.size();}
        vector<int>::iterator begin(){return s.begin();}
        vector<int>::iterator end(){return s.end();}
    };
    vector<EqClass> ecs;
    vector<int> W;
    vector<int> tag(M.n,false);
    vector<int> inW;
    ecs.resize(2);
    for(int i=0;i<M.n;i++){
        bel[i]=M.acc[i];
        ecs[M.acc[i]].push_back(i);
    }
    if(ecs[0].size()<=ecs[1].size()){
        W.push_back(0);
        inW.push_back(1);
        inW.push_back(0);
    }else{
        W.push_back(1);
        inW.push_back(0);
        inW.push_back(1);
    }
    while(!W.empty()){
        int u=W.back();
        W.pop_back();
        inW[u]=0;
        for(int c=0;c<M.Sig;c++){
            vector<int> todo;
            for(auto s:ecs[u]){
                for(auto y:deltaf[s][c]){
                    if(tag[y]) continue;
                    if(!ecs[bel[y]].cnt) todo.push_back(bel[y]);
                    ecs[bel[y]].cnt++;
                    tag[y]=1;
                }
            }
            for(auto i:todo){
                if(ecs[i].cnt!=ecs[i].size()){
                    vector<int> B[2];
                    for(auto y: ecs[i]) B[tag[y]].push_back(y);
                    if(B[1].size()<B[0].size()) swap(B[1],B[0]);
                    for(auto y:B[1]) bel[y]=ecs.size();
                    if(inW[i]){
                        inW.push_back(true);
                        W.push_back(ecs.size());
                    }else{
                        W.push_back(i);
                        inW[i]=true;
                        inW.push_back(false);
                    }
                    ecs[i].s=move(B[0]);
                    ecs.emplace_back(move(B[1]));
                    for(auto y:ecs.back()){
                        tag[y]=false;
                    }
                }
                ecs[i].cnt=0;
                for(auto y:ecs[i]){
                    tag[y]=false;
                }
            }
        }
    }
    int cnt=0;
    vector<int> reid(ecs.size(),0);//在新的DFA上重编号
    for(int i=0;i<(int)ecs.size();i++){
        reid[i]=cnt++;
    }
    DFA res(cnt,M.Sig,reid[bel[M.st]]);
    for(int i=0;i<M.n;i++){
        for(int j=0;j<M.Sig;j++){
            res.delta[bel[i]][j]=bel[M.delta[i][j]];
        }
        if(M.acc[i]){
            res.acc[reid[bel[i]]]=1;
        }
    }
    return res;
}

该算法复杂度为 \mathcal O (n |\Sigma| \log n )。

如何证明？在 Hopcroft 的论文中视 |\Sigma| 为常数后使用了平摊分析得到复杂度为 \mathcal O (n \log n)，在 Knuutila 的论文中 5. Time analysis 部分通过对划分树（partition tree）染色的办法得到复杂度为 \mathcal O (n\log n)。后来，有人构造了一种情况使得 Hopcroft 算法达到复杂度上界 \Theta (n \log n)，并且 \Omega(n\log n) 是 DFA 最小化的理论复杂度下限。

由于本文篇幅实在太长了，所以这里不展开具体的证明。

值得一提的是在中文互联网上几乎没有复杂度正确的 Hopcroft 算法。本人翻了 Bing 搜索前 5 面的内容，除了 CSDN 收费内容看不了之外，只有 OI-wiki 上的代码复杂度是正确的。大多数错误代码都没有构建 \delta^{-1}，直接 \mathcal O(n) 的遍历了整个状态集，导致复杂度错误。

自动机在 OI 的运用

各类字符串算法与自动机的关系

很多字符串算法本身就是一个 DFA，大部分只需要补出失配状态即可。

字典树：只接受某些字符串的 DFA。

KMP 自动机：只接受以某个字符串为后缀的字符串的 DFA。

AC 自动机：只接受某个字符串集的后缀的 DFA。

后缀自动机：只接受某个字符串的后缀的自动机。

子序列自动机：只接受某个字符串的子序列的自动机。

其中 KMP 自动机、后缀自动机和子序列自动机是天然满足最小化的。

DP 套 DP

很有意思的一类 DP。我个人更喜欢将其称为在 FSM 上 DP。其中的 FSM 一般都是 DFA。

比如 AT_agc022_e [AGC022E] Median Replace。

题意：称一个长度为奇数的 01 串是美丽字符串当且仅当可以通过 \frac{n-1}2 次如下操作，使最终字符串为唯一字符 1。

操作：选择连续 3 个比特，用中位数代替。

求一个部分位置未知的 01 串有多少种决定未知方案满足这个串是美丽的。

先画一下操作的真值表。

记所有美丽字符串构成的语言为 L。（当然，长度为偶数的串均不是美丽串）

考虑构造一个 DFA，接受美丽的字符串。

对于 01 序列和括号序列，有一个经典的分析办法是令 h:\{0,1\} \to \{1,-1\},h(0)=-1,h(1)=-1,\Phi(a)= \sum_{i=1} ^n h(a_i)。

观察上述操作，得到处理 \texttt{000} \to 0 和 \texttt{111} \to 1 外 \Phi 是不变的，其它的操作相当于相近让 0 和 1 抵消。我们需要的结果是长为 1 的全 1 串，所以感性上我们希望尽量多的保留 1，减少 0。所以我们遇到 \texttt{000} 是一定要抵消两个 0 的。然后我们不大希望 1 和 1 抵消所以这是放到最后做的。所以第二步做的是 0 和 1 的抵消（相当于无条件）。

从感性上理解这是对的。按照这样构造了一个这样的自动机（结点标签抵消后的后缀）：

digraph MP{
  rankdir=LR;
  node[shape=circle]
  ε[color=red];
  0;
  1[shape=doublecircle];
  10;
  100;
  00;
  11[shape=doublecircle];
  ε -> 0 [label=0]
  ε -> 1 [label=1]
  0 -> 00 [label=0]
  00 -> 0 [label=0]
  0 -> ε [label=1]
  00 -> 0 [label=1]
  1 -> 10 [label=0]
  1 -> 11 [label=1]
  10 -> 100 [label=0]
  100 -> 10 [label=0]
  100 -> 10 [label=1]
  11 -> 11 [label=1]
  11 -> 11 [label=0]
  10 -> 1 [label=1]
}

自动机有关的习题

不是很多，随便放了几道。

• Median Replace Hard
• P12294 [THUPC 2025 决赛] 一个 01 串，n 次三目运算符，最后值为 1（加强版）
• AT_abc418_g [ABC418G] Binary Operation
• CF1142D Foreigner
• P10436 [JOIST 2024] 卡牌收集 / Card Collection

参考资料

• OI Wiki 有限状态自动机；
• 国家集训队 2021 论文集 徐哲安 浅谈有限状态自动机及其应用，可以在 OI-wiki/libs Github 或 OIerTFX/IOI Github 获得。
• Hopcroft J .An N Log N Algorithm for Minimizing States in a Finite Automaton[J].Theory of Machines & Computations, 1971.DOI:10.1016/B978-0-12-417750-5.50022-1.
• Knuutila T .Re-describing an algorithm by Hopcroft[J].Theoretical Computer Science, 2001, 250(1-2):333-363.DOI:10.1016/S0304-3975(99)00150-4.

版权声明

本文由作者 MZMTab 发表在博客园和洛谷专栏，两处内容的不同仅为了适配不同的 Markdown 渲染引擎。

采用 CC BY-NC-SA 4.0 协议授权，转载须注明出处，演绎作品须使用相同协议共享。

本文的 Markdown 源码在博客园可以获得。在遵守上述协议的条件下您可以自由地使用。