自动机理论
自动机理论
自动机入门
-
自动机是一个数学模型，它可以对于一个信号序列进行判定。
-
自动机的结构是一张有向图。
-
自动机的每个节点表示一个状态，自动机的边可以接受多种字符。
形式化定义
对于 确定性有穷状态自动机（DFA） 来说，有以下部分：
- 字符集（\(\sum\)），自动机可以接受的字符。
- 状态集合（\(Q\)），把 DFA 看作有向图时，状态相当于图上的顶点。
- 起始状态（\(q_0\)），\(q_0 \in Q\)。
- 接受状态集合（\(F\)），\(F \in Q\)。
- 转移函数（\(\delta\)），\(\delta\) 接受一个状态和一个字符集中的字符，返回一个新的状态，相当于图上的边。
DFA 可以识别字符串，接受它或者拒绝它。
形式化地讲，就是：
\(S = w_1w_2\cdots w_n,w_i \in \sum\).
\(r_0 = q_0 , r_i \gets \delta(r_{i-1},w_i)\).
若 \(r_n \in F\) 则 DFA 接受了串 \(S\)，否则拒绝串 \(S\)。
简单的例子
Trie
我们的 Trie 树就是一个简单的自动机。
它接受一个字符串 \(t\)，判定 \(t\) 是否在给定集合 \(S\) 中。
这个就是一个简单的接受字符串 \(\{\texttt{xing},\texttt{xu},\texttt{xin}\}\) 的 Trie。加粗的节点是接受的状态。
KMP
KMP 也可以看作一个自动机。
它判断一个串 \(t\) 是否包含子串 \(s\)。
一些练习与例子
看看一些其他的 DFA，感受一下它的工作方式和强大之处。
在看之前可以尝试自行构建一个...
例一
\(\sum = \{0,1\}, p \in N^+\).
接受“包含 \(\texttt1\) 的个数是 \(p\) 的倍数”的串。
例：\(p = 3\)，接受 \(\texttt{111},\texttt{001011},\texttt{000}\)，拒绝 \(\texttt{10},\texttt{1001}\)。
这个 DFA 就很简单。
例二
\(\sum = \{0,1\},p \in N^+\).
接受“\(p\) 的倍数的二进制表示”的串，允许有前导零。
例：\(p = 5\)，接受 \(\texttt{101},\texttt{01010},\text{000}\)，拒绝 \(\texttt{11},\texttt{0001}\)。
思路：对于一个数 \(n\)，当我们输入新的一位，如果是 \(0\)，那么就变成 \(n \times 2\)；如果输入 \(1\)，那么变成 \(n \times 2 + 1\)。之后我们按照模 \(5\) 的余数建立状态，发现这样就可以根据数字变化，确定新的余数，在余数间转移了。
这样就可以建立一个接受“\(5\) 的倍数的二进制表示”的串的自动机。
NFA
NFA，非确定性有穷状态自动机。
NFA 和 DFA 差不多，但是 NFA 的状态转移函数每次返回一个集合（可能是空集）而不是一个状态。实际上可以转移到集合中的任何一个状态，这也是“非确定性”的来源。
举个例子：
这个 NFA 接受的是“以 \(1\) 结尾的 \(\texttt{01}\) 串“。可以看出，从 \(p\) 出发有两条弧都以 \(1\) 进行转移。
\(\epsilon\)-NFA
\(\epsilon\)-NFA 可以接受标记为 \(\epsilon\) 的转移弧，表示无条件转移——不需要输入任何字符即可转移。
举个例子：
这就是一个 \(\epsilon\)-NFA。它接受的是“\(0\) 的个数或 \(1\) 的个数为偶数”的串。
对于 \(\epsilon\)-NFA，我们一般会把它转化为等价的 NFA。具体地，先求出“\(\epsilon\)-闭包”，之后把转移 \(\delta(q,c) = S\) 变成 \(\delta(q,c) = S'\)，\(S'\) 为 \(S\) 中所有状态的 \(\epsilon\)-闭包的并集。其实就是类似于缩点的过程。
不过这样的 NFA 可能会有多种起始状态。
一些例题
来源：《算法竞赛入门经典》
UVA1671 语言的历史 History of Languages
题意：
给定两个 DFA，判断是否等价。
题解：
书上的方法是：两个 DFA 等价可以转化为“\(a\) 的补和 \(b\) 不相交，\(b\) 的补和 \(a\) 不相交”。可以构造 DFA 的补（交换终态和非终态），之后尝试构造新的 DFA，让它的每个状态都是 \((q_1,q_2)\)，\(q_1\) 和 \(q_2\) 分别是两个 DFA 中的状态。这样把问题转化为找一个新的 DFA 接受的串。
对于转移不存在的情况，加一个废物状态，把所有不存在的转移都转移到它即可。
这里可以直接利用异或判断是否合法。对于某个状态，\(a\ \text{xor}\ b = 0\) 表示它们同时接受或者同时不接受，即等价。之后进行一个大力 DFS 即可。