自動機術語

自動機有如下基本概念：

符號

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

字

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

字母表

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

語言

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

Kleene閉包

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

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

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

自動機是有限狀態(tài)機(FSM)的數(shù)學模型。

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

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

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

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

下面是三類有限自動機

確定有限自動機(DFA)

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

非確定有限自動機(NFA)

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

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

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

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

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

自動機PDA

PDA(下推自動機)這種機器等同于 DFA (或 NFA)，除了它們額外的裝備了棧形式的內存。轉移函數(shù) δ 也依賴于在棧頂?shù)姆?，并在每次轉移時指定如何變更棧。非確定 PDA 接受上下文無關語言。

自動機LBA

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

自動機圖靈機

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

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

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

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

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

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

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

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

自動機編程的技術常用在以自動機原理為基礎的算法中，例如形式語言分析[1]。

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

自動機是有限狀態(tài)機(FSM)的數(shù)學模型。FSM 是給定符號輸入，依據(jù)(可表達為一個表格的)轉移函數(shù)“跳轉”過一系列狀態(tài)的一種機器。在常見的 FSM 的“Mealy”變體中，這個轉移函數(shù)告訴自動機給定當前狀態(tài)和當前字符的時候下一個狀態(tài)是什么。

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

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

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

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

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

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

自動機可分為有限自動機、后進先出自動機、線性有界自動機、圖靈機等幾種。它們對語言的識別能力各不相同。