自动机
自动机是一种对信号序列进行判定的数学模型
一，主观理解
以上为自动机的定义，该定义十分抽象，以下为笔者的主观理解。
1. 自动机建立的基础
即定义中的“信号序列”。
我们可以把这个所谓“信号序列”理解为一个串，串的每一位上存有信息。
eg. 字符串是一个“信号序列”，数组是一个“信号序列”，一个数的各位可以构成一个“信号序列”。
自动机便是建立在信号序列的基础上的。
2. 自动机要干什么
即定义中的“判定”。
对针对信号序列的特定命题给出真或假的回答。
eg. 判断一个数是奇数还是偶数是判定，判断一个字符串是否回文是判定，判断一个字符串是否是一特定字符串的子串是判定。
3. 自动机的具象化理解
虽然自动机是一个抽象的数学模型，但在 OI 里，自动机常可以被理解为一张有向图，我们把自动机所求的判定拆解为若干小判定，每一个结点都代表某次判定时的状态，结点向结点转移便是判定的过程，判定会有多种结果，因而一个结点的不同子结点便代表判定的不同结果。
以下图片有助于更好地理解：
eg. 在 Trie 树上查找某字符串是否出现时，Trie 树便可视为自动机的一个实现，它针对一些特定文本串建立（信号序列），并完成对某字符串是否出现的判断（判定）。
二，形式化理解
一个有限状态自动机（DFA）由以下五部分构成：
- 字符集（\(\Sigma\)）：该自动机只能输入这些字符。
- 状态集合（\(Q\)）：将自动机看作有向图，其图上结点即表示状态。
- 起始状态（\(\text{start}\)）：\(\text{start}\in Q\)。
- 接受状态集合（\(F\)）：\(F\subseteq Q\)。
- 转移函数（\(\delta\)）：接受两个参数返回一个值的函数，参数其一与返回值均为状态，另一参数为字符集中字符（若将自动机看作有向图，则第一参数为点，第二参数为其出边，返回值为出边指向的结点）
当 DFA 读入一个字符串时，会从起始状态开始按转移函数进行转移，读入结束后若指针指向接收状态，则称该自动机 \(A\) 接受字符串 \(S\)，\(A(S)=\text{True}\)；反之则称该自动机 \(A\) 不接受字符串 \(S\)，\(A(S)=\text{False}\)。
空状态：如果一个状态 \(v\)，对于字符 \(c\)，不存在转移，则令 \(\delta(v,c)=\text{null}\)，即一个空状态，空状态表示不接受，且无法继续转移至任何一个接收状态。
若令转移函数 \(\delta\) 可以接受字符串，则 \(\delta(v,s)=\delta(\delta(v,s[1]),s[2...|s|])\)。
$ $ A(s)=[(start,s)F] $ $