确定有限状态自动机概念笔记

本文介绍了 DFA 的相关概念。

写在前面

0xfaner 花了不少时间学习字符串算法,发现自动机理论占据了非常重要的地位。无论是SAM,PAM还是ACAM,哪怕是最基础的KMP都和 DFA 有着紧密的联系。所以 0xfaner 整理了一下自动机理论以巩固自己的知识点,也帮助后来者在这方面少走点弯路。

本文参考:OI-wiki

简介

确定有限状态自动机,英文名 deterministic finite automaton,简称 DFA。

DFA 由以下五部分构成:

  1. 字符集 $\Sigma$ ,该自动机只能输入这些字符。

  2. 状态集合 $Q$ 。如果把一个 DFA 看作一个 DAG ,那么 DFA 中的状态就相当于 DAG 上的顶点。

  3. 起始状态 $Start$ , $Start \in Q$ ,是一个特殊的状态。起始状态一般用 $s$ 表示,为了避免混淆,本文中使用 $Start$ 。

  4. 接受状态集合 $F$ , $F \subseteq Q$ 是一组特殊的状态。

  5. 转移函数 $\delta$ , $\delta$ 是一个接受两个参数返回一个值的函数,形如 $\delta(v,c)=v’$ ,其中 $v$ 和 $v’$ 都是一个状态, $c$ 是 $\Sigma$ 中的一个字符。如果把一个 DFA 看作一个 DAG ,那么 DFA 中的转移函数就相当于顶点间的边,而每条边上都有一个字符。

DFA 的作用就是识别字符串,一个自动机 $A$ ,若它能识别(接受)字符串 $S$ ,那么 $A(S)=True$ ,否则 $A(S)=False$ 。

当一个 DFA 检验一个字符串时,从初始状态起依照转移函数进行转移。如果最终停留在一个接受状态,那么我们称这个 DFA 接受这个字符串,反之我们称这个 DFA 不接受这个字符串。

如果一个状态 $v$ 没有字符 $c$ 的转移,记 $\delta(v,c)=null$ 。其中 $null \notin F$ ,代指所有无法转移到任意一个接收状态的状态。即 $null$ 只能转移到 $null$ 。

拓展一下 $\delta$ ,使得 $\delta$ 的第二个参数能够接受一个字符串,记作 $\delta(v,s)=\delta(\delta(\delta(v,s[0]),s[1]),…)=v’$ ,形象的理解就是把多次字符转移压缩表示。根据定义容易得到 $A(s)=[\delta(Start,s)\in F]$ 。

算法竞赛中常见的自动机

字典树

字典树是最简单的一类自动机,也是大部分人学到的第一个自动机算法。

基于字符串集合 $\{s_1, s_2, \dots, s_n\}$ 的字典树接受且仅接受 $s_i(1 \leq i \leq n)$ 。

转移函数就是 Trie 上的边,接受状态是将每个字符串插入到 Trie 时到达的那个状态。

KMP 自动机

KMP算法可以视作自动机。

基于字符串 $s$ 的KMP自动机接受且仅接受以 $s$ 为后缀的字符串,其接受状态为 $|s|$ 。

转移函数:

对于 KMP 的更深入探究,戳 KMP算法探究

AC 自动机

基于字符串集合 $\{s_1, s_2, \dots, s_n\}$ 的 AC 自动机接受且仅接受以 $s_i(1 \leq i \leq n)$ 为后缀的字符串。

可以视作 Trie 和 KMP 的结合。

对于 AC 自动机的更深入探究,戳 AC自动机算法探究

后缀自动机

基于字符串 $s$ 的后缀自动机接受且仅接受 $s$ 的后缀。

对于后缀自动机的更深入探究,戳 后缀自动机算法探究

广义后缀自动机

基于字符串集合 $\{s_1, s_2, \dots, s_n\}$ 的广义后缀自动机自动机接受且仅接受 $s_i(1 \leq i \leq n)$ 的后缀。

广义后缀自动机与后缀自动机的关系就是 AC 自动机与 KMP 自动机的关系。

回文自动机

回文自动机比较特殊,它不能非常方便地定义为自动机。

基于字符串 $s$ 的回文自动机接受且仅接受 $s$ 的所有回文子串的中心及右半部分。

“中心及右边部分”在奇回文串中就是字面意思,在偶回文串中定义为一个特殊字符加上右边部分。这个定义看起来很奇怪,但它能让回文自动机真正成为一个自动机,而不仅是两棵树。

序列自动机

基于字符串 $s$ 的序列自动机接受且仅接受 $s$ 的子序列。