自動(dòng)機(jī)

下面是三類有限自動(dòng)機(jī)

確定有限自動(dòng)機(jī)(DFA)

自動(dòng)機(jī)的每個(gè)狀態(tài)都有對(duì)字母表中所有符號(hào)的轉(zhuǎn)移。

非確定有限自動(dòng)機(jī)(NFA)

自動(dòng)機(jī)的狀態(tài)對(duì)字母表中的每個(gè)符號(hào)可以有也可以沒有轉(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è)字。

有ε轉(zhuǎn)移的非確定有限自動(dòng)機(jī)(FND-ε或ε-NFA)

除了有能力對(duì)任何符號(hào)跳轉(zhuǎn)到更多狀態(tài)或沒有狀態(tài)可以跳轉(zhuǎn)之外，它們可以做根本不關(guān)于符號(hào)的跳轉(zhuǎn)。就是說，如果一個(gè)狀態(tài)有標(biāo)記著 ε 的轉(zhuǎn)移，則 NFA 可以處在 ε-轉(zhuǎn)移可到達(dá)的任何狀態(tài)中，直接或通過其他有 ε-轉(zhuǎn)移的狀態(tài)。從一個(gè)狀態(tài) q 通過這種方法可到達(dá)的狀態(tài)的集合叫做 q 的 ε-閉包。

盡管可以證明所有這些自動(dòng)機(jī)都「可以接受同樣的語(yǔ)言」。你總是可以構(gòu)造接受與給定的 NFA M 同樣語(yǔ)言的某個(gè) DFA M。

自動(dòng)機(jī)是有限狀態(tài)機(jī)(FSM)的數(shù)學(xué)模型。

FSM 是給定符號(hào)輸入，依據(jù)(可表達(dá)為一個(gè)表格的)轉(zhuǎn)移函數(shù)“跳轉(zhuǎn)”過一系列狀態(tài)的一種機(jī)器。在常見的 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è)字寫在其上的磁帶，通過自動(dòng)機(jī)的讀磁頭來(lái)讀取它；磁頭在磁帶上前行移動(dòng)，一次讀一個(gè)符號(hào))。一旦輸入被耗盡，自動(dòng)機(jī)被稱為“停止”了。

依賴自動(dòng)機(jī)停止時(shí)的狀態(tài)，稱呼這個(gè)自動(dòng)機(jī)要么是“接受”要么“拒絕”這個(gè)輸入。如果停止于“接受狀態(tài)”，則自動(dòng)機(jī)“接受”了這個(gè)字。在另一方面，如果它停止于“拒絕狀態(tài)”，則這個(gè)字被“拒絕”。自動(dòng)機(jī)接受的所有字的集合被稱為“這個(gè)自動(dòng)機(jī)接受的語(yǔ)言”。

自動(dòng)機(jī) automaton 原來(lái)是模仿人和動(dòng)物的行動(dòng)而做成的機(jī)器人的意思。但是現(xiàn)已被抽象化為如下的機(jī)器。時(shí)間是離散的（t=0，1，2……），在每一個(gè)時(shí)刻它處于所存在的有限個(gè)內(nèi)部狀態(tài)中的一個(gè)。對(duì)每一個(gè)時(shí)刻給予有限個(gè)輸入中的一個(gè)。那么下一個(gè)時(shí)刻的內(nèi)部狀態(tài)就由現(xiàn)在的輸入和現(xiàn)在的內(nèi)部狀態(tài)所決定。每個(gè)時(shí)刻的輸出只由那個(gè)時(shí)刻的內(nèi)部狀態(tài)所決定。作為自動(dòng)機(jī)的例子可以舉出由McCulloch-pitts的神經(jīng)模型組合所得到的神經(jīng)網(wǎng)絡(luò)模型、數(shù)字計(jì)算機(jī)等。

自動(dòng)機(jī)有如下基本概念：

符號(hào)

有某種意義或在這個(gè)機(jī)器上有效的任意數(shù)據(jù)(datum)。符號(hào)有時(shí)就叫做“字母”。

字

通過一些符號(hào)串接而形成的有限字符串。

字母表

符號(hào)的有限集合。字母表經(jīng)常指示為 Σ，它是在字母表中所有字母的集合。

語(yǔ)言

字的集合，由給定字母表中的符號(hào)形成。可以是也可以不是無(wú)限的。

Kleene閉包

一個(gè)語(yǔ)言可以被認(rèn)為是所有可能字的子集。所有可能字的集合可以被認(rèn)為是所有可能的字符串串接的集合。形式上說，所有可能字符串的集合叫做自由幺半群。它被指示為 Σ ，上標(biāo) * 被稱為Kleene星號(hào)。

注意，自動(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)是被接受還是被拒絕。

一般的說，自動(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è)度量是足夠的小。自動(dòng)機(jī)廣泛應(yīng)用于工業(yè)生產(chǎn)上。

確定有限狀態(tài)自動(dòng)機(jī)與非確定有限狀態(tài)自動(dòng)機(jī)識(shí)別的語(yǔ)言都是正則語(yǔ)言。由于正則語(yǔ)言的良好性質(zhì)，許多為其他自動(dòng)機(jī)（下推自動(dòng)機(jī)或圖靈機(jī)）不能判定的問題，在有限狀態(tài)自動(dòng)機(jī)的情形下，都可以得到判定，并且存在有效的演算法。

對(duì)一個(gè)確定有限狀態(tài)自動(dòng)機(jī) ，下述判定問題都可以判定，并且存在有效的演算法。

該自動(dòng)機(jī)識(shí)別的語(yǔ)言是否為空集。

該自動(dòng)機(jī)識(shí)別的語(yǔ)言是否為有限集。

該自動(dòng)機(jī)是否與另一個(gè)確定有限狀態(tài)自動(dòng)機(jī)識(shí)別同一個(gè)的語(yǔ)言。

對(duì)信號(hào)序列進(jìn)行邏輯處理的裝置。在自動(dòng)控制領(lǐng)域內(nèi)，是指離散數(shù)字系統(tǒng)的動(dòng)態(tài)數(shù)學(xué)模型，可定義為一種邏輯結(jié)構(gòu)，一種算法或一種符號(hào)串變換。自動(dòng)機(jī)這一術(shù)語(yǔ)也廣泛出現(xiàn)在許多其他相關(guān)的學(xué)科中，分別有不同的內(nèi)容和研究目標(biāo)。在計(jì)算機(jī)科學(xué)中自動(dòng)機(jī)用作計(jì)算機(jī)和計(jì)算過程的動(dòng)態(tài)數(shù)學(xué)模型，用來(lái)研究計(jì)算機(jī)的體系結(jié)構(gòu)、邏輯操作、程序設(shè)計(jì)乃至計(jì)算復(fù)雜性理論。在語(yǔ)言學(xué)中則把自動(dòng)機(jī)作為語(yǔ)言識(shí)別器，用來(lái)研究各種形式語(yǔ)言。 在神經(jīng)生理學(xué)中把自動(dòng)機(jī)定義為神經(jīng)網(wǎng)絡(luò)的動(dòng)態(tài)模型，用來(lái)研究神經(jīng)生理活動(dòng)和思維規(guī)律，探索人腦的機(jī)制。在生物學(xué)中有人把自動(dòng)機(jī)作為生命體的生長(zhǎng)發(fā)育模型，研究新陳代謝和遺傳變異。在數(shù)學(xué)中則用自動(dòng)機(jī)定義可計(jì)算函數(shù)，研究各種算法。現(xiàn)代自動(dòng)機(jī)的一個(gè)重要特點(diǎn)是能與外界交換信息，并根據(jù)交換得來(lái)的信息改變自己的動(dòng)作，即改變自己的功能，甚至改變自己的結(jié)構(gòu)，以適應(yīng)外界的變化。也就是說在一定程度上具有類似于生命有機(jī)體那樣的適應(yīng)環(huán)境變化的能力。

自動(dòng)機(jī)與一般機(jī)器的重要區(qū)別在于自動(dòng)機(jī)具有固定的內(nèi)在狀態(tài)，即具有記憶能力和識(shí)別判斷能力或決策能力，這正是現(xiàn)代信息處理系統(tǒng)的共同特點(diǎn)。因此，自動(dòng)機(jī)適宜于作為信息處理系統(tǒng)乃至一切信息系統(tǒng)的數(shù)學(xué)模型。自動(dòng)機(jī)可按其變量集和函數(shù)的特性分類，也可按其抽象結(jié)構(gòu)和聯(lián)結(jié)方式分類。主要有：有限自動(dòng)機(jī)和無(wú)限自動(dòng)機(jī)、線性自動(dòng)機(jī)和非線性自動(dòng)機(jī)、確定型自動(dòng)機(jī)和不確定型自動(dòng)機(jī)、同步自動(dòng)機(jī)和異步自動(dòng)機(jī)、級(jí)聯(lián)自動(dòng)機(jī)和細(xì)胞自動(dòng)機(jī)等。

上述自動(dòng)機(jī)接受的語(yǔ)言家族被稱為正規(guī)語(yǔ)言(Regular Expression)。更強(qiáng)力的自動(dòng)機(jī)可以接受更復(fù)雜的語(yǔ)言。比如:

自動(dòng)機(jī)PDA

PDA(下推自動(dòng)機(jī))這種機(jī)器等同于 DFA (或 NFA)，除了它們額外的裝備了棧形式的內(nèi)存。轉(zhuǎn)移函數(shù) δ 也依賴于在棧頂?shù)姆?hào)，并在每次轉(zhuǎn)移時(shí)指定如何變更棧。非確定 PDA 接受上下文無(wú)關(guān)語(yǔ)言。

自動(dòng)機(jī)LBA

LBA （線性有界自動(dòng)機(jī)）是有限制的 圖靈機(jī)；不使用無(wú)限磁帶，它的磁帶有同輸入字元串成正比的空間。LBA 接受上下文有關(guān)語(yǔ)言。

自動(dòng)機(jī)圖靈機(jī)

它們是最強(qiáng)力的電腦器。它們擁有磁帶形式的無(wú)限內(nèi)存，和可以讀取和變更磁帶的磁頭，它可在磁帶上向任何方向移動(dòng)。圖靈機(jī)等價(jià)于演算法，是現(xiàn)代電腦的理論基礎(chǔ)。圖靈機(jī)判定遞歸語(yǔ)言并識(shí)別遞歸可枚舉語(yǔ)言。

自動(dòng)機(jī)編程的技術(shù)常用在以自動(dòng)機(jī)原理為基礎(chǔ)的算法中，例如形式語(yǔ)言分析[1]。

約翰遜等在1968年發(fā)表的《Automatic generation of efficient lexical processors using finite state techniques》論文是早期提到自動(dòng)機(jī)編程的論文[2]。 Peter Naur在1963年的論文將自動(dòng)機(jī)編程當(dāng)成一種通用的軟件技術(shù)[3]。作者將此技術(shù)稱為“圖靈機(jī)的方法”，不過此論文是以自動(dòng)機(jī)的狀態(tài)及步驟為基礎(chǔ)，沒有提到圖靈機(jī)。

自動(dòng)機(jī)是有限狀態(tài)機(jī)(FSM)的數(shù)學(xué)模型。FSM 是給定符號(hào)輸入，依據(jù)(可表達(dá)為一個(gè)表格的)轉(zhuǎn)移函數(shù)“跳轉(zhuǎn)”過一系列狀態(tài)的一種機(jī)器。在常見的 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è)字寫在其上的磁帶，通過自動(dòng)機(jī)的讀磁頭來(lái)讀取它；磁頭在磁帶上前行移動(dòng)，一次讀一個(gè)符號(hào))。一旦輸入被耗盡，自動(dòng)機(jī)被稱為“停止”了。

依賴自動(dòng)機(jī)停止時(shí)的狀態(tài)，稱呼這個(gè)自動(dòng)機(jī)要么是“接受”要么“拒絕”這個(gè)輸入。如果停止于“接受狀態(tài)”，則自動(dòng)機(jī)“接受”了這個(gè)字。在另一方面，如果它停止于“拒絕狀態(tài)”，則這個(gè)字被“拒絕”。自動(dòng)機(jī)接受的所有字的集合被稱為“這個(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)是被接受還是被拒絕。

一般的說，自動(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è)度量是足夠的小 。

常見自動(dòng)機(jī)有以下幾種：以電話交換機(jī)為主要實(shí)例的有限自動(dòng)機(jī)，是自動(dòng)機(jī)理論的基礎(chǔ)，被應(yīng)用到自動(dòng)控制，生物系統(tǒng)中；由下推表組成的單項(xiàng)非確定程序的下推自動(dòng)機(jī)；線性有界自動(dòng)機(jī)；用來(lái)描述通用計(jì)算機(jī)計(jì)算能力的圖靈機(jī)模型；進(jìn)行與轉(zhuǎn)移函數(shù)，轉(zhuǎn)移狀態(tài)有關(guān)輸出的時(shí)序機(jī)；由一些基本語(yǔ)句構(gòu)成程序框圖的波斯特機(jī)；隨即存儲(chǔ)機(jī)；堆棧自動(dòng)機(jī)；不受有限自動(dòng)機(jī)做控制器和存儲(chǔ)限制的無(wú)限自動(dòng)機(jī)；統(tǒng)計(jì)自動(dòng)機(jī)某一條件概率分布的概率自動(dòng)機(jī)和細(xì)胞自動(dòng)機(jī)。

數(shù)理語(yǔ)言學(xué)中研究抽象自動(dòng)機(jī)的理論。抽象自動(dòng)機(jī)是一種能夠識(shí)別語(yǔ)言的抽象的裝置，它不是具有物理實(shí)體的機(jī)器，而是表示計(jì)算機(jī)運(yùn)算方式的抽象的邏輯關(guān)系系統(tǒng)，這樣的抽象自動(dòng)機(jī)可以用來(lái)檢驗(yàn)輸入的符號(hào)串是不是語(yǔ)言中合格的句子，如果是合格的句子，自動(dòng)機(jī)就接收它，如果不是，就不接收它。如圖1所示：

自動(dòng)機(jī)可分為有限自動(dòng)機(jī)、后進(jìn)先出自動(dòng)機(jī)、線性有界自動(dòng)機(jī)、圖靈機(jī)等幾種。它們對(duì)語(yǔ)言的識(shí)別能力各不相同。