Theme NexT works best with JavaScript enabled

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

本文介绍了 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 $ 的子序列。