自動機

計算機控制系統的控制程式具有有限狀態自動機（FA）的特徵，可以用有限狀態機理論來描述。有限自動機（Finite Automata Machine）是計算機科學的重要基石，它在軟體開發領域內通常被稱作有限狀態機（Finite State Machine），是一種套用非常廣泛的軟體設計模式。

基本介紹

• 中文名：自動機
• 外文名：automata
• 定義：是有限狀態機(FSM)的數學模型
• 套用範圍：廣泛套用於工業生產上
• 重要特點：能與外界交換信息，並改變動作
• 重要區別：在於自動機具有固定的內在狀態

簡介

自動機是有限狀態機(FSM)的數學模型。

FSM 是給定符號輸入，依據(可表達為一個表格的)轉移函式“跳轉”過一系列狀態的一種機器。在常見的 FSM 的“Mealy”變體中，這個轉移函式告訴自動機給定當前狀態和當前字元的時候下一個狀態是什麼。

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

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

自動機 automaton 原來是模仿人和動物的行動而做成的機器人的意思。但是現已被抽象化為如下的機器。時間是離散的（t=0，1，2……），在每一個時刻它處於所存在的有限個內部狀態中的一個。對每一個時刻給予有限個輸入中的一個。那么下一個時刻的內部狀態就由現在的輸入和現在的內部狀態所決定。每個時刻的輸出只由那個時刻的內部狀態所決定。作為自動機的例子可以舉出由McCulloch-pitts的神經模型組合所得到的神經網路模型、數字計算機等。

形式描述

對信號序列進行邏輯處理的裝置。在自動控制領域內，是指離散數字系統的動態數學模型，可定義為一種邏輯結構，一種算法或一種符號串變換。自動機這一術語也廣泛出現在許多其他相關的學科中，分別有不同的內容和研究目標。在計算機科學中自動機用作計算機和計算過程的動態數學模型，用來研究計算機的體系結構、邏輯操作、程式設計乃至計算複雜性理論。在語言學中則把自動機作為語言識別器，用來研究各種形式語言。在神經生理學中把自動機定義為神經網路的動態模型，用來研究神經生理活動和思維規律，探索人腦的機制。在生物學中有人把自動機作為生命體的生長發育模型，研究新陳代謝和遺傳變異。在數學中則用自動機定義可計算函式，研究各種算法。現代自動機的一個重要特點是能與外界交換信息，並根據交換得來的信息改變自己的動作，即改變自己的功能，甚至改變自己的結構，以適應外界的變化。也就是說在一定程度上具有類似於生命有機體那樣的適應環境變化的能力。

自動機與一般機器的重要區別在於自動機具有固定的內在狀態，即具有記憶能力和識別判斷能力或決策能力，這正是現代信息處理系統的共同特點。因此，自動機適宜於作為信息處理系統乃至一切信息系統的數學模型。自動機可按其變數集和函式的特性分類，也可按其抽象結構和聯結方式分類。主要有：有限自動機和無限自動機、線性自動機和非線性自動機、確定型自動機和不確定型自動機、同步自動機和異步自動機、級聯自動機和細胞自動機等。

術語

自動機有如下基本概念：

符號

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

字

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

字母表

符號的有限集合。字母表經常指示為 Σ，它是在字母表中所有字母的集合。

語言

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

Kleene閉包

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

形式描述

自動機可以表示為5-元組，這裡的:

Q 是狀態的非空有窮集合。

∑ 是符號的有限集合，我們稱為這個自動機接受的語言的字母表。 輸入字元串都是∑上的字元串

δ 是狀態轉移函式，就是（右2）。

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

q0 是開始狀態，就是說自動機在還未處理輸入的時候的狀態(明顯的 q0∈ Q)。

F 是終止狀態集合，也叫做接受狀態的 Q 中的狀態的集合(就是 F⊆Q)。

分類

下面是三類有限自動機

確定有限自動機(DFA)

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

非確定有限自動機(NFA)

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

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

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

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

擴展

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

PDA

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

LBA

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

圖靈機

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

能力判定

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

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

該自動機識別的語言是否為空集。

該自動機識別的語言是否為有限集。

該自動機是否與另一個確定有限狀態自動機識別同一個的語言。

注意事項

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

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