基本描述
自動(dòng)機(jī)是有限狀態(tài)機(jī)(FSM)的數(shù)學(xué)模型。FSM 是給定符號(hào)輸入，依據(jù)(可表達(dá)為一個(gè)表格的)轉(zhuǎn)移函數(shù)“跳轉(zhuǎn)”過(guò)一系列狀態(tài)的一種機(jī)器。在常見(jiàn)的 FSM 的“Mealy”變體中，這個(gè)轉(zhuǎn)移函數(shù)告訴自動(dòng)機(jī)給定當(dāng)前狀態(tài)和當(dāng)前字符的時(shí)候下一個(gè)狀態(tài)是什么。
逐個(gè)讀取輸入中的符號(hào)，直到被完全耗盡(把它當(dāng)作有一個(gè)字寫(xiě)在其上的磁帶，通過(guò)自動(dòng)機(jī)的讀磁頭來(lái)讀取它；磁頭在磁帶上前行移動(dòng)，一次讀一個(gè)符號(hào))。一旦輸入被耗盡，自動(dòng)機(jī)被稱(chēng)為“停止”了。
依賴(lài)自動(dòng)機(jī)停止時(shí)的狀態(tài)，稱(chēng)呼這個(gè)自動(dòng)機(jī)要么是“接受”要么“拒絕”這個(gè)輸入。如果停止于“接受狀態(tài)”，則自動(dòng)機(jī)“接受”了這個(gè)字。在另一方面，如果它停止于“拒絕狀態(tài)”，則這個(gè)字被“拒絕”。自動(dòng)機(jī)接受的所有字的集合被稱(chēng)為“這個(gè)自動(dòng)機(jī)接受的語(yǔ)言”。
但要注意，自動(dòng)機(jī)一般不必須有有限數(shù)目甚至可數(shù)個(gè)狀態(tài)。比如，量子有限自動(dòng)機(jī)有不可數(shù)無(wú)限個(gè)狀態(tài)，因?yàn)樗锌赡軤顟B(tài)的集合是在復(fù)投影空間中所有點(diǎn)的集合。所以，量子有限自動(dòng)機(jī)和有限狀態(tài)機(jī)一樣，都是更一般想法拓?fù)渥詣?dòng)機(jī)的特殊情況，它的狀態(tài)的集合是拓?fù)淇臻g，而狀態(tài)轉(zhuǎn)移函數(shù)取自在這個(gè)空間上的所有可能函數(shù)。拓?fù)渥詣?dòng)機(jī)經(jīng)常叫做 M-自動(dòng)機(jī)，簡(jiǎn)單是半自動(dòng)機(jī)加上接受狀態(tài)集合的補(bǔ)充，這里的集合交集確定初始狀態(tài)是被接受還是被拒絕。
一般的說(shuō)，自動(dòng)機(jī)不需要嚴(yán)格的接受或拒絕一個(gè)輸入；它可以按某個(gè)在零和一之間的概率接受它。還是用量子有限自動(dòng)機(jī)作為展示例子，它只按某個(gè)概率接受輸入。這個(gè)想法也是更一般情況幾何自動(dòng)機(jī)或度量自動(dòng)機(jī)的特殊情況，它的狀態(tài)的集合是度量空間，一個(gè)語(yǔ)言被這個(gè)自動(dòng)機(jī)接受如果在初始點(diǎn)和接受狀態(tài)的集合之間的距離關(guān)于這個(gè)度量是足夠的小。
[編輯] 術(shù)語(yǔ)
自動(dòng)機(jī)有如下基本概念：
符號(hào)
有某種意義或在這個(gè)機(jī)器上有效的任意數(shù)據(jù)(datum)。符號(hào)有時(shí)就叫做“字母”。
字
通過(guò)一些符號(hào)串接而形成的有限字符串。
字母表
符號(hào)的有限集合。字母表經(jīng)常指示為 Σ，它是在字母表中所有字母的集合。
語(yǔ)言
字的集合，由給頂字母表中的符號(hào)形成。可以是也可以不是無(wú)限的。
Kleene閉包
一個(gè)語(yǔ)言可以被認(rèn)為是所有可能字的子集。所有可能字的集合可以被認(rèn)為是所有可能的字符串串接的集合。形式上說(shuō)，所有可能字符串的集合叫做自由幺半群。它被指示為 Σ * ，上標(biāo) * 被稱(chēng)為 Kleene星號(hào)。
[編輯] 形式描述
自動(dòng)機(jī)可以表示為5-元組 
，這里的:
- Q 是狀態(tài)的集合。
- ∑ 是符號(hào)的有限集合，我們稱(chēng)為這個(gè)自動(dòng)機(jī)接受的語(yǔ)言的字母表。
- δ 是轉(zhuǎn)移函數(shù)，就是
。
(對(duì)于非確定自動(dòng)機(jī)，空串是允許的輸入)。
- q0 是開(kāi)始狀態(tài)，就是說(shuō)自動(dòng)機(jī)在還未處理輸入的時(shí)候的狀態(tài)(明顯的 q0∈ Q)。
- F 是叫做接受狀態(tài)的 Q 中的狀態(tài)的集合(就是 F?Q)。
給定一個(gè)輸入字母 
，可以使用簡(jiǎn)單的 currying 技巧寫(xiě)轉(zhuǎn)移函數(shù)為 
，就是說(shuō)，寫(xiě) δ(q,a) = δa(q) 對(duì)于所有
。這種方式下轉(zhuǎn)移可以被更簡(jiǎn)單的看待: 它就是“動(dòng)作”于 Q 中一個(gè)狀態(tài)上的生成另一個(gè)狀態(tài)的某種東西。你可以接著考慮重復(fù)的應(yīng)用函數(shù)復(fù)合于各種函數(shù) δa, δb 等等的結(jié)果。重復(fù)的函數(shù)復(fù)合形成一個(gè)幺半群。對(duì)于轉(zhuǎn)移函數(shù)，這個(gè)幺半群叫做轉(zhuǎn)移幺半群，有時(shí)也叫做“變換半群”。
給定一對(duì)字母 
，可以通過(guò)堅(jiān)持 
定義一個(gè)新函數(shù) 
，這里的 
指示函數(shù)復(fù)合。明顯的，可以遞歸的繼續(xù)這個(gè)過(guò)程，這樣就有了為所有字 
定義的函數(shù) 
的遞歸定義，因此有了映射
這個(gè)構(gòu)造也可以反過(guò)來(lái): 給定 
，可以重新構(gòu)造一個(gè) δ，因此兩個(gè)描述是等價(jià)的。
三元組 
被稱(chēng)為半自動(dòng)機(jī)。半自動(dòng)機(jī)位于自動(dòng)機(jī)底下，它們就是忽略了開(kāi)始狀態(tài)和接受狀態(tài)的自動(dòng)機(jī)。開(kāi)始狀態(tài)和接受狀態(tài)的補(bǔ)充概念允許自動(dòng)機(jī)做半自動(dòng)機(jī)不能做的事情: 它們可以識(shí)別形式語(yǔ)言。確定有限自動(dòng)機(jī) 
接受的語(yǔ)言 L 是:
就是說(shuō)，一個(gè)自動(dòng)機(jī)所接受的語(yǔ)言是在字母表 Σ 之上所有字 w 的集合，當(dāng)給定為自動(dòng)機(jī)的輸入的時(shí)候，將導(dǎo)致它停止于 F 中的某個(gè)狀態(tài)。被自動(dòng)機(jī)接受的語(yǔ)言叫做可識(shí)別語(yǔ)言。
當(dāng)狀態(tài)集合 Q 是有限的時(shí)候，自動(dòng)機(jī)被稱(chēng)為有限狀態(tài)自動(dòng)機(jī)，而所有可識(shí)別的語(yǔ)言是正則語(yǔ)言。事實(shí)上，有一個(gè)強(qiáng)等價(jià): 對(duì)于所有正則語(yǔ)言，都有一個(gè)有限狀態(tài)自動(dòng)機(jī)，反之亦然。
如上所述，集合 Q 不必須是有限或可數(shù)的；它可以采用一般的拓?fù)淇臻g；這就得到了一般的拓?fù)渥詣?dòng)機(jī)。另一種可能的推廣是度量自動(dòng)機(jī)或“幾何自動(dòng)機(jī)”。在這種情況下，改變了對(duì)語(yǔ)言的接受: 替代在 
中的最終狀態(tài)的集合包含，以在最終狀態(tài) 
和集合 F 之間的度量距離的方式給出。特定類(lèi)型的概率自動(dòng)機(jī)是度量自動(dòng)機(jī)，其度量空間是在概率空間上的測(cè)量。
[編輯] 有限自動(dòng)機(jī)的分類(lèi)
下面是三類(lèi)有限自動(dòng)機(jī)
確定有限自動(dòng)機(jī)(DFA)
對(duì)字母表中每個(gè)符號(hào)，自動(dòng)機(jī)的狀態(tài)都有且僅有一個(gè)轉(zhuǎn)移。
DFA
非確定有限自動(dòng)機(jī)(NFA)
自動(dòng)機(jī)的狀態(tài)對(duì)字母表中的每個(gè)符號(hào)可以有也可以沒(méi)有轉(zhuǎn)移，對(duì)一個(gè)符號(hào)甚至可以有多個(gè)轉(zhuǎn)移。自動(dòng)機(jī)接受一個(gè)字，如果存在至少一個(gè)從 q0 到 F 中標(biāo)記(label)著這個(gè)輸入字的一個(gè)狀態(tài)的路徑。如果一個(gè)轉(zhuǎn)移是“未定義”的，自動(dòng)機(jī)因此不知道如何繼續(xù)讀取輸入，則拒絕這個(gè)字。
等價(jià)于前面例子 DFA 的 NFA
有ε轉(zhuǎn)移的非確定有限自動(dòng)機(jī)(FND-ε或ε-NFA)
除了有能力對(duì)任何符號(hào)跳轉(zhuǎn)到更多狀態(tài)或沒(méi)有狀態(tài)可以跳轉(zhuǎn)之外，它們可以做根本不關(guān)于符號(hào)的跳轉(zhuǎn)。就是說(shuō)，如果一個(gè)狀態(tài)有標(biāo)記著 ε 的轉(zhuǎn)移，則 NFA 可以處在 ε-轉(zhuǎn)移可到達(dá)的任何狀態(tài)中，直接或通過(guò)其他有 ε-轉(zhuǎn)移的狀態(tài)。從一個(gè)狀態(tài) q 通過(guò)這種方法可到達(dá)的狀態(tài)的集合叫做 q 的 ε-閉包。
盡管可以證明所有這些自動(dòng)機(jī)都“可以接受同樣的語(yǔ)言”。你總是可以構(gòu)造接受與給定的 NFA M 同樣語(yǔ)言的某個(gè) DFA M。
[編輯] 有限自動(dòng)機(jī)的擴(kuò)展
上述自動(dòng)機(jī)接受的語(yǔ)言家族被稱(chēng)為正則語(yǔ)言家族。更強(qiáng)力的自動(dòng)機(jī)可以接受更復(fù)雜的語(yǔ)言。比如:
下推自動(dòng)機(jī)(PDA)
這種機(jī)器等同于 DFA (或 NFA)，除了它們額外的裝備了棧形式的內(nèi)存。轉(zhuǎn)移函數(shù) δ 也依賴(lài)于在棧頂?shù)姆?hào)，并在每次轉(zhuǎn)移時(shí)指定如何變更棧。非確定 PDA 接受上下文無(wú)關(guān)語(yǔ)言。
線性有界自動(dòng)機(jī)(LBA)
LBA 是有限制的圖靈機(jī)；不使用無(wú)限磁帶，它的磁帶有同輸入字符串成正比的空間。LBA 接受上下文有關(guān)語(yǔ)言。
圖靈機(jī)
它們是最強(qiáng)力的計(jì)算機(jī)器。它們擁有磁帶形式的無(wú)限內(nèi)存，和可以讀取和變更磁帶的磁頭，它可在磁帶上向任何方向移動(dòng)。圖靈機(jī)等價(jià)于算法，是現(xiàn)代計(jì)算機(jī)的理論基礎(chǔ)。圖靈機(jī)判定遞歸語(yǔ)言并識(shí)別遞歸可枚舉語(yǔ)言。
[編輯] 有限狀態(tài)自動(dòng)機(jī)的最小化
根據(jù) Myhill-Nerode定理，在同構(gòu)意義下接受一個(gè)正則語(yǔ)言的最少狀態(tài)的確定有限狀態(tài)自動(dòng)機(jī)是唯一的。同時(shí)我們還存在有效的算法（時(shí)間開(kāi)銷(xiāo)是O(n2)的）構(gòu)造出與給定確定有限狀態(tài)自動(dòng)機(jī)等價(jià)的最小化的確定有限狀態(tài)自動(dòng)機(jī)。
[編輯] 計(jì)算能力與判定問(wèn)題
確定有限狀態(tài)自動(dòng)機(jī)與非確定有限狀態(tài)自動(dòng)機(jī)識(shí)別的語(yǔ)言都是正則語(yǔ)言。由于正則語(yǔ)言的良好性質(zhì)，許多為其他自動(dòng)機(jī)（下推自動(dòng)機(jī)或圖靈機(jī)）不能判定的問(wèn)題，在有限狀態(tài)自動(dòng)機(jī)的情形下，都可以得到判定，并且存在有效的算法。
對(duì)一個(gè)確定有限狀態(tài)自動(dòng)機(jī)，下述判定問(wèn)題都可以判定，并且存在有效的算法。
- 該自動(dòng)機(jī)識(shí)別的語(yǔ)言是否為空集。
- 該自動(dòng)機(jī)識(shí)別的語(yǔ)言是否為有限集。
- 該自動(dòng)機(jī)是否與另一個(gè)確定有限狀態(tài)自動(dòng)機(jī)識(shí)別同一個(gè)的語(yǔ)言。
[編輯] 外部鏈接
[編輯] 引用
- John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman - Introduction to Automata Theory, Languages, and Computation (2nd Edition)
- Michael Sipser（1997）．Introduction to the Theory of Computation．PWS Publishing．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.
取自"