跳转至

自動機

OI 中所説的「自動機」一般都指「確定有限狀態自動機」。

自動機是 OI、計算機科學中被廣泛使用的一個數學模型，其思想在許多字符串算法中都有涉及，因此推薦在學習一些字符串算法（KMP、AC 自動機、SAM）前先完成自動機的學習。學習自動機有助於理解上述算法。

前置知識

  • 基礎圖論。

自動機入門

首先理解一下自動機是用來幹什麼的：自動機是一個對信號序列進行判定的數學模型。

這句話涉及到的名詞比較多，逐一解釋一下。「信號序列」是指一連串有順序的信號，例如字符串從前到後的每一個字符、數組從 1 到 n 的每一個數、數從高到低的每一位等。「判定」是指針對某一個命題給出或真或假的回答。有時我們需要對一個信號序列進行判定。一個簡單的例子就是判定一個二進制數是奇數還是偶數，較複雜的例子例如判定一個字符串是否迴文，判定一個字符串是不是某個特定字符串的子序列等等。

自動機的工作原理和地圖很類似。假設你在你家，然後你從你家到學校，按順序經過了很多路口。每個路口都有岔路，而你在所有這些路口的選擇就構成了一個序列。

例如，你的選擇序列是「家門 -> 右拐 -> 萍水西街 -> 尚園街 -> 古墩路 -> 地鐵站 -> 下寧橋」，那你按順序經過的路口可能是「家 -> 家門口 -> 萍水西街競舟北路口 -> 萍水西街尚圓街路口 -> 尚園街古墩路口 -> 古墩路中 -> 三壩地鐵站 -> 下寧橋地鐵站」。可以發現，上學的選擇序列不止這一個。同樣要去地鐵站，你還可以從競舟北路繞道，或者橫穿文鼎苑抄近路。

而我們如果找到一個選擇序列，就可以在地圖上比劃出這個選擇序列能不能去學校。比如，如果一個選擇序列是「家門 -> 右拐 -> 萍水西街 -> 尚園街 -> 古墩路 -> 地鐵站 -> 錢江路 -> 四號線站台 -> 聯莊」，那麼它就不會帶你去同一個學校，但是仍舊可能是一個可被接受的序列，因為目標地點可能不止一個。

也就是説，我們通過這個地圖和一組目的地，將信號序列分成了三類，一類是無法識別的信號序列（例如「家門 -> ???」），一類是能去學校的信號序列，另一類是不能的信號序列。我們將所有合法的信號序列分成了兩類，完成了一個判定問題。

既然自動機是一個數學模型，那麼顯然不可能是一張地圖。對地圖進行抽象之後，可以簡化為一個有向圖。因此，自動機的結構就是一張有向圖。

而自動機的工作方式和流程圖類似，不同的是：自動機的每一個結點都是一個判定結點；自動機的結點只是一個單純的狀態而非任務；自動機的邊可以接受多種字符（不侷限於 T 或 F）。

例如，完成「判斷一個二進制數是不是偶數」的自動機如下：

example automaton

從起始結點開始，從高到低接受這個數的二進制序列，然後看最終停在哪裏。如果最終停在紅圈結點，則是偶數，否則不是。

如果需要判定一個有限的信號序列和另外一個信號序列的關係（例如另一個信號序列是不是某個信號序列的子序列），那麼常用的方法是針對那個有限的信號序列構建一個自動機。這個在學習 KMP 的時候會講到。

需要注意的是，自動機只是一個 數學模型，而 不是算法，也 不是數據結構。實現同一個自動機的方法有很多種，可能會有不一樣的時空複雜度。

接下來你可以選擇繼續看自動機的形式化定義，也可以去學習 KMP、AC 自動機 或 SAM。

形式化定義

一個 確定有限狀態自動機（DFA） 由以下五部分構成：

  1. 字符集（\(\Sigma\)），該自動機只能輸入這些字符。
  2. 狀態集合（\(Q\)）。如果把一個 DFA 看成一張有向圖，那麼 DFA 中的狀態就相當於圖上的頂點。
  3. 起始狀態（\(start\)），\(start\in Q\)，是一個特殊的狀態。起始狀態一般用 \(s\) 表示，為了避免混淆，本文中使用 \(start\)。
  4. 接受狀態集合（\(F\)），\(F\subseteq Q\)，是一組特殊的狀態。
  5. 轉移函數（\(\delta\)），\(\delta\) 是一個接受兩個參數返回一個值的函數，其中第一個參數和返回值都是一個狀態，第二個參數是字符集中的一個字符。如果把一個 DFA 看成一張有向圖，那麼 DFA 中的轉移函數就相當於頂點間的邊，而每條邊上都有一個字符。

DFA 的作用就是識別字符串，一個自動機 \(A\)，若它能識別（接受）字符串 \(S\)，那麼 \(A(S)=\mathrm{True}\)，否則 \(A(S)=\mathrm{False}\)。

當一個 DFA 讀入一個字符串時，從初始狀態起按照轉移函數一個一個字符地轉移。如果讀入完一個字符串的所有字符後位於一個接受狀態，那麼我們稱這個 DFA 接受 這個字符串，反之我們稱這個 DFA 不接受 這個字符串。

如果一個狀態 \(v\) 沒有字符 \(c\) 的轉移，那麼我們令 \(\delta(v,c)=\mathrm{null}\)，而 \(\mathrm{null}\) 只能轉移到 \(\mathrm{null}\)，且 \(\mathrm{null}\) 不屬於接受狀態集合。無法轉移到任何一個接受狀態的狀態都可以視作 \(\mathrm{null}\)，或者説，\(\mathrm{null}\) 代指所有無法轉移到任何一個接受狀態的狀態。

我們擴展定義轉移函數 \(\delta\)，令其第二個參數可以接收一個字符串：\(\delta(v,s)=\delta(\delta(v,s[1]),s[2..|s|])\)，擴展後的轉移函數就可以表示從一個狀態起接收一個字符串後轉移到的狀態。那麼，\(A(s)=[\delta(start,s)\in F]\)。

如，一個接受且僅接受字符串 "a", "ab", "aac" 的 DFA：

OI 中常用的自動機

字典樹

字典樹 是大部分 OIer 接觸到的第一個自動機，接受且僅接受指定的字符串集合中的元素。

轉移函數就是 Trie 上的邊，接受狀態是將每個字符串插入到 Trie 時到達的那個狀態。

KMP 自動機

KMP 算法 可以視作自動機，基於字符串 \(s\) 的 KMP 自動機接受且僅接受以 \(s\) 為後綴的字符串，其接受狀態為 \(|s|\)。

轉移函數：

\[ \delta(i, c)= \begin{cases} i+1&s[i+1]=c\\ 0&s[1]\ne c\land i=0\\ \delta(\pi(i),c)&s[i+1]\ne c\land i>0 \end{cases} \]

AC 自動機

AC 自動機 接受且僅接受以指定的字符串集合中的某個元素為後綴的字符串。也就是 Trie + KMP。

後綴自動機

後綴自動機 接受且僅接受指定字符串的後綴。

廣義後綴自動機

廣義後綴自動機 接受且僅接受指定的字符串集合中的某個元素的後綴。也就是 Trie + SAM。

廣義 SAM 與 SAM 的關係就是 AC 自動機與 KMP 自動機的關係。

迴文自動機

迴文自動機 比較特殊，它不能非常方便地定義為自動機。

如果需要定義的話，它接受且僅接受某個字符串的所有迴文子串的 中心及右半部分。

「中心及右邊部分」在奇迴文串中就是字面意思，在偶迴文串中定義為一個特殊字符加上右邊部分。這個定義看起來很奇怪，但它能讓 PAM 真正成為一個自動機，而不僅是兩棵樹。

序列自動機

序列自動機 接受且僅接受指定字符串的子序列。

後綴鏈接

由於自動機和匹配有着密不可分的關係，而匹配的一個基本思想是「這個串不行，就試試它的後綴可不可以」，所以在很多自動機（KMP、AC 自動機、SAM、PAM）中，都有後綴鏈接的概念。

一個狀態會對應若干字符串，而這個狀態的後綴鏈接，是在自動機上的、是這些字符串的公共真後綴的字符串中，最長的那一個。

一般來講，後綴鏈接會形成一棵樹，並且不同自動機的後綴鏈接樹有着一些相同的性質，學習時可以加以注意。

擴展閲讀

在計算複雜性領域中，自動機是一個經典的模型。並且，自動機與正則語言有着密不可分的關係。

如果對相關內容感興趣的話，推薦閲讀博客 計算複雜性（1）Warming Up: 自動機模型。

本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用