自動機理論是一種將離散數學系統的構造，作用和關係作為研究對象的數學理論。
在理論計算機科學中，自動機理論是對抽象機和它們能解決的問題的研究。自動機理論密切關聯於形式語言理論，因為自動機經常按它們所能識別的形式語言類來分類。
基本介紹
- 中文名：自動機理論
- 外文名：automata theory
- 領域：數學理論
- 關聯：形式語言理論
簡介,術語,詳細內容,計算能力與判定問題,理論發展,
簡介
自動機是有限狀態機(FSM)的數學模型。FSM 是給定符號輸入，依據(可表達為一個表格的)轉移函式“跳轉”過一系列狀態的一種機器。在常見的 FSM 的“Mealy”變體中，這個轉移函式告訴自動機給定當前狀態和當前字元的時候下一個狀態是什麼。
逐個讀取輸入中的符號，直到被完全耗盡(把它當作有一個字寫在其上的磁帶，通過自動機的讀磁頭來讀取它；磁頭在磁帶上前行移動，一次讀一個符號)。一旦輸入被耗盡，自動機被稱為“停止”了。
依賴自動機停止時的狀態，稱呼這個自動機要么是“接受”要么“拒絕”這個輸入。如果停止於“接受狀態”，則自動機“接受”了這個字。在另一方面，如果它停止於“拒絕狀態”，則這個字被“拒絕”。自動機接受的所有字的集合被稱為“這個自動機接受的語言”。
但要注意，自動機一般不必須有有限數目甚至可數個狀態。比如，量子有限自動機有不可數無限個狀態，因為所有可能狀態的集合是在復投影空間中所有點的集合。所以，量子有限自動機和有限狀態機一樣，都是更一般想法拓撲自動機的特殊情況，它的狀態的集合是拓撲空間，而狀態轉移函式取自在這個空間上的所有可能函式。拓撲自動機經常叫做M-自動機，簡單是半自動機加上接受狀態集合的補充，這裡的集合交集確定初始狀態是被接受還是被拒絕。
一般的說，自動機不需要嚴格的接受或拒絕一個輸入；它可以按某個在零和一之間的機率接受它。還是用量子有限自動機作為展示例子，它只按某個機率接受輸入。這個想法也是更一般情況幾何自動機或度量自動機的特殊情況，它的狀態的集合是度量空間，一個語言被這個自動機接受如果在初始點和接受狀態的集合之間的距離關於這個度量是足夠的小。
術語
自動機有如下基本概念：
符號 ：有某種意義或在這個機器上有效的任意數據(datum)。符號有時就叫做“字母”。
字：通過一些符號串接而形成的有限字元串。
字母表 ：符號的有限集合。字母表經常指示為Sigma ，它是在字母表中所有字母的集合。
語言 ：字的集合，由給頂字母表中的符號形成。可以是也可以不是無限的。
Kleene閉包 ：一個語言可以被認為是所有可能字的子集。所有可能字的集合可以被認為是所有可能的字元串串接的集合。形式上說，所有可能字元串的集合叫做自由么半群。它被指示為 Sigma *}，上標 * 被稱為Kleene星號。
詳細內容
常見自動機有以下幾種：以電話交換機為主要實例的有限自動機，是自動機理論的基礎，被套用到自動控制，生物系統中；由下推表組成的單項非確定程式的下推自動機；線性有界自動機；用來描述通用計算機計算能力的圖靈機模型；進行與轉移函式，轉移狀態有關輸出的時序機；由一些基本語句構成程式框圖的波斯特機；隨即存儲機；堆疊自動機；不受有限自動機做控制器和存儲限制的無限自動機；統計自動機某一條件機率分布的機率自動機和細胞自動機。
數理語言學中研究抽象自動機的理論。抽象自動機是一種能夠識別語言的抽象的裝置，它不是具有物理實體的機器，而是表示計算機運算方式的抽象的邏輯關係系統，這樣的抽象自動機可以用來檢驗輸入的符號串是不是語言中合格的句子，如果是合格的句子，自動機就接收它，如果不是，就不接收它。如圖所示： 
自動機理論
自動機理論自動機可分為有限自動機、後進先出自動機、線性有界自動機、圖靈機等幾種。它們對語言的識別能力各不相同。
計算能力與判定問題
確定有限狀態自動機與非確定有限狀態自動機識別的語言都是正則語言。由於正則語言的良好性質，許多為其他自動機（下推自動機或圖靈機）不能判定的問題，在有限狀態自動機的情形下，都可以得到判定，並且存在有效的算法。
對一個確定有限狀態自動機，下述判定問題都可以判定，並且存在有效的算法。
該自動機識別的語言是否為空集；
該自動機識別的語言是否為有限集；
該自動機是否與另一個確定有限狀態自動機識別同一個的語言。
理論發展
美國語言學家N.喬姆斯基等人建立了形式文法和自動機之間的聯繫，證明語言的形式文法與自動機之間存在著如下的對應關係：①若某一語言能用圖靈機來識別，則它就能用 O型文法生成，反之亦然；②若某一語言能用線性有界自動機來識別，則它就能用上下文敏感文法生成，反之亦然；③若某一語言能用後進先出自動機來識別，則它就能用上下文自由文法生成，反之亦然；④若某一語言能用有限自動機來識別，則它就能用有限狀態文法生成，反之亦然。
