自動機理論

在理論電腦科學中，自動機理論是對抽象機和它們能解決的問題的研究。自動機理論密切關聯於形式語言理論，因為自動機經常按它們所能辨識的形式語言類來分類。

基本描述

自動機是有限狀態機（FSM）的數學模型。FSM是給定符號輸入，依據（可表達為一個表格的）轉移函數「跳轉」過一系列狀態的一種機器。在常見的FSM的「米利型有限狀態機」（Mealy）變體中，這個轉移函數告訴自動機給定當前狀態和當前字元的時候下一個狀態是什麼。

逐個讀取輸入中的符號，直到被完全耗盡(把它當作有一個字寫在其上的磁帶，通過自動機的讀磁頭來讀取它；磁頭在磁帶上前行移動，一次讀一個符號)。一旦輸入被耗盡，自動機被稱為「停止」了。

依賴自動機停止時的狀態，稱呼這個自動機要麼是「接受」要麼「拒絕」這個輸入。如果停止於「接受狀態」，則自動機「接受」了這個字。在另一方面，如果它停止於「拒絕狀態」，則這個字被「拒絕」。自動機接受的所有字的集合被稱為「這個自動機接受的語言」。

但要注意，自動機一般不必須有有限數目甚至可數個狀態。比如，量子有限自動機有不可數無限個狀態，因為所有可能狀態的集合是在復投影空間中所有點的集合。所以，量子有限自動機和有限狀態機一樣，都是更一般想法拓撲自動機的特殊情況，它的狀態的集合是拓撲空間，而狀態轉移函數取自在這個空間上的所有可能函數。拓撲自動機經常叫做 M-自動機，簡單是半自動機加上接受狀態集合的補充，這裏的集合交集確定初始狀態是被接受還是被拒絕。

一般地說，自動機不需要嚴格的接受或拒絕一個輸入；它可以按某個在零和一之間的概率接受它。還是用量子有限自動機作為展範例子，它只按某個概率接受輸入。這個想法也是更一般情況幾何自動機或度量自動機的特殊情況，它的狀態的集合是度量空間，一個語言被這個自動機接受如果在初始點和接受狀態的集合之間的距離關於這個度量是足夠的小。

術語

自動機有如下基本概念：

符號

有某種意義或在這個機器上有效的任意數據(datum)。符號有時就叫做「字母」。

字

通過一些符號串接而形成的有限字串。

字母表

符號的有限集合。字母表經常指示為 ${\displaystyle \Sigma }$，它是在字母表中所有字母的集合。

語言

字的集合，由給定字母表中的符號形成。可以是也可以不是無限的。

Kleene閉包

一個語言可以被認為是所有可能字的子集。所有可能字的集合可以被認為是所有可能的字串串接的集合。形式上說，所有可能字串的集合叫做自由么半群。它被指示為 ${\displaystyle \Sigma ^{*}}$，上標 * 被稱為 Kleene星號。

形式描述

自動機可以表示為5-元組 ${\displaystyle \langle Q,\Sigma ,\delta ,q_{0},F\rangle }$，這裏的:

• Q 是狀態的集合。
• ∑ 是符號的有限集合，我們稱為這個自動機接受的語言的字母表。
• δ 是轉移函數，就是

${\displaystyle \delta :Q\times \Sigma \rightarrow Q}$。

(對於非確定自動機，空字串是允許的輸入)。

• q₀ 是開始狀態，就是說自動機在還未處理輸入的時候的狀態(明顯的 q₀∈ Q)。
• F 是叫做終止狀態的 Q 中的狀態的集合(就是 F⊆Q)。

給定一個輸入字母 ${\displaystyle a\in \Sigma }$，可以使用簡單的 currying 技巧寫轉移函數為 ${\displaystyle \delta _{a}:Q\rightarrow Q}$，就是說，寫 ${\displaystyle \delta (q,a)=\delta _{a}(q)}$ 對於所有${\displaystyle q\in Q}$。這種方式下轉移可以被更簡單的看待: 它就是「動作」於 Q 中一個狀態上的生成另一個狀態的某種東西。你可以接着考慮重複的應用函數複合於各種函數 ${\displaystyle \delta _{a}}$, ${\displaystyle \delta _{b}}$ 等等的結果。重複的函數複合形成一個么半群。對於轉移函數，這個么半群叫做轉移么半群，有時也叫做「變換半群」。

給定一對字母 ${\displaystyle a,b\in \Sigma }$，可以通過堅持 ${\displaystyle {\widehat {\delta }}_{ab}=\delta _{a}\circ \delta _{b}}$ 定義一個新函數 ${\displaystyle {\widehat {\delta }}}$，這裏的 ${\displaystyle \circ }$ 指示函數複合。明顯的，可以遞歸的繼續這個過程，這樣就有了為所有字 ${\displaystyle w\in \Sigma ^{*}}$ 定義的函數 ${\displaystyle {\widehat {\delta }}_{w}}$ 的遞歸定義，因此有了對映

${\displaystyle {\widehat {\delta }}:Q\times \Sigma ^{\star }\rightarrow Q.}$

這個構造也可以反過來: 給定 ${\displaystyle {\widehat {\delta }}}$，可以重新構造一個 ${\displaystyle \delta }$，因此兩個描述是等價的。

三元組 ${\displaystyle \langle Q,\Sigma ,\delta \rangle }$ 被稱為半自動機。半自動機位於自動機底下，它們就是忽略了開始狀態和接受狀態的自動機。開始狀態和接受狀態的補充概念允許自動機做半自動機不能做的事情: 它們可以辨識形式語言。確定有限自動機 ${\displaystyle \langle Q,\Sigma ,\delta ,q_{0},F\rangle }$ 接受的語言 ${\displaystyle L}$ 是:

${\displaystyle L=\{w\in \Sigma ^{\star }\,|\;{\widehat {\delta }}(q_{0},w)\in F\}}$

就是說，一個自動機所接受的語言是在字母表 ${\displaystyle \Sigma }$ 之上所有字 w 的集合，當給定為自動機的輸入的時候，將導致它停止於 ${\displaystyle F}$ 中的某個狀態。被自動機接受的語言叫做可辨識語言。

當狀態集合 Q 是有限的時候，自動機被稱為有限狀態自動機，而所有可辨識的語言是正則語言。事實上，有一個強等價: 對於所有正則語言，都有一個有限狀態自動機，反之亦然。

如上所述，集合 Q 不必須是有限或可數的；它可以採用一般的拓撲空間；這就得到了一般的拓撲自動機。另一種可能的推廣是度量自動機或「幾何自動機」。在這種情況下，改變了對語言的接受: 替代在 ${\displaystyle {\widehat {\delta }}(q_{0},w)\in F}$ 中的最終狀態的集合包含，以在最終狀態 ${\displaystyle {\widehat {\delta }}(q_{0},w)}$ 和集合 ${\displaystyle F}$ 之間的度量距離的方式給出。特定類型的概率自動機是度量自動機，其度量空間是在概率空間上的測量。

有限自動機的分類

下面是三類有限自動機

確定有限自動機(DFA)

對字母表中每個符號，自動機的狀態都有且僅有一個轉移。

DFA

非確定有限自動機(NFA)

自動機的狀態對字母表中的每個符號可以有也可以沒有轉移，對一個符號甚至可以有多個轉移。自動機接受一個字，如果存在至少一個從 q₀ 到 F 中標記(label)着這個輸入字的一個狀態的路徑。如果一個轉移是「未定義」的，自動機因此不知道如何繼續讀取輸入，則拒絕這個字。

等價於前面例子 DFA 的 NFA

有ε轉移的非確定有限自動機(FND-ε或ε-NFA)

除了有能力對任何符號跳轉到更多狀態或沒有狀態可以跳轉之外，它們可以做根本不關於符號的跳轉。就是說，如果一個狀態有標記着 ${\displaystyle \epsilon }$ 的轉移，則 NFA 可以處在 ${\displaystyle \epsilon }$-轉移可到達的任何狀態中，直接或通過其他有 ${\displaystyle \epsilon }$-轉移的狀態。從一個狀態 q 通過這種方法可到達的狀態的集合叫做 q 的 ${\displaystyle \epsilon }$-閉包。

儘管可以證明所有這些自動機都「可以接受同樣的語言」。你總是可以構造接受與給定的 NFA M 同樣語言的某個 DFA M。

有限自動機的擴充

上述自動機接受的語言家族被稱為正則語言家族。更強力的自動機可以接受更複雜的語言。比如:

下推自動機(PDA)

這種機器等同於 DFA (或 NFA)，除了它們額外的裝備了棧形式的主記憶體。轉移函數 ${\displaystyle \delta }$ 也依賴於在棧頂的符號，並在每次轉移時指定如何變更棧。非確定 PDA 接受上下文無關語言。

線性有界自動機(LBA)

LBA 是有限制的圖靈機；不使用無限磁帶，它的磁帶有同輸入字串成正比的空間。LBA 接受上下文有關語言。

圖靈機

它們是最強力的電腦器。它們擁有磁帶形式的無限主記憶體，和可以讀取和變更磁帶的磁頭，它可在磁帶上向任何方向移動。圖靈機等價於演算法，是現代電腦的理論基礎。圖靈機判定遞歸語言並辨識遞歸可列舉語言。

有限狀態自動機的最小化

主條目：確定有限狀態自動機最小化

根據 Myhill-Nerode定理，在同構意義下接受一個正則語言的最少狀態的確定有限狀態自動機是唯一的。同時我們還存在有效的演算法（時間開銷是O(n²)的）構造出與給定確定有限狀態自動機等價的最小化的確定有限狀態自動機。

計算能力與判定問題

確定有限狀態自動機與非確定有限狀態自動機辨識的語言都是正則語言。由於正則語言的良好性質，許多為其他自動機（下推自動機或圖靈機）不能判定的問題，在有限狀態自動機的情形下，都可以得到判定，並且存在有效的演算法。

對一個確定有限狀態自動機，下述判定問題都可以判定，並且存在有效的演算法。

• 該自動機辨識的語言是否為空集。
• 該自動機辨識的語言是否為有限集。
• 該自動機是否與另一個確定有限狀態自動機辨識同一個的語言。

外部連結

• Visual Automata Simulator （頁面存檔備份，存於互聯網檔案館）
• JFLAP （頁面存檔備份，存於互聯網檔案館）
• Proyecto SEPa (in Spanish) （頁面存檔備份，存於互聯網檔案館）
• Exorciser (in German) （頁面存檔備份，存於互聯網檔案館）

參照

• John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman - Introduction to Automata Theory, Languages, and Computation (2nd Edition)
• Michael Sipser. Introduction to the Theory of Computation. PWS Publishing. 1997. ISBN 0-534-94728-X. Part One: Automata and Languages, chapters 1–2, pp.29–122. Section 4.1: Decidable Languages, pp.152–159. Section 5.1: Undecidable Problems from Language Theory, pp.172–183.