自動機理論

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

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

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

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

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

自動機有如下基本概念：

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

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

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

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

Kleene閉包 ：一個語言可以被認為是所有可能字的子集。所有可能字的集合可以被認為是所有可能的字符串串接的集合。形式上説，所有可能字符串的集合叫做自由幺半羣。它被指示為 Sigma *}，上標 * 被稱為Kleene星號 ^[2]  。

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

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

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

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

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

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

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

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

美國語言學家N.喬姆斯基等人建立了形式文法和自動機之間的聯繫，證明語言的形式文法與自動機之間存在着如下的對應關係：①若某一語言能用圖靈機來識別，則它就能用 O型文法生成，反之亦然；②若某一語言能用線性有界自動機來識別，則它就能用上下文敏感文法生成，反之亦然；③若某一語言能用後進先出自動機來識別，則它就能用上下文自由文法生成，反之亦然；④若某一語言能用有限自動機來識別，則它就能用有限狀態文法生成，反之亦然。

這種關於形式文法與自動機的關係，反映了語言的生成過程與識別過程的內在聯繫，它已成為計算機科學的基石之一。這是語言學對於現代自然科學發生影響的一個明證。