自動(dòng)機(jī)理論是理論計(jì)算機(jī)科學(xué)和數(shù)理語(yǔ)言學(xué)中研究抽象自動(dòng)機(jī)及其解決問(wèn)題能力的理論。抽象自動(dòng)機(jī)是一種能夠識(shí)別語(yǔ)言的抽象裝置，它們經(jīng)常按它們所能識(shí)別的形式語(yǔ)言類(lèi)來(lái)分類(lèi)。
基本介紹
自動(dòng)機(jī)是有限狀態(tài)機(jī)(FSM)的數(shù)學(xué)模型。FSM 是給定符號(hào)輸入，依據(jù)(可表達(dá)為一個(gè)表格的)轉(zhuǎn)移函數(shù)“跳轉(zhuǎn)”過(guò)一系列狀態(tài)的一種機(jī)器。在常見(jiàn)的 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è)字寫(xiě)在其上的盒式錄音磁帶，通過(guò)自動(dòng)機(jī)的讀磁頭來(lái)讀取它；磁頭在磁帶上前行移動(dòng)，一次讀一個(gè)符號(hào))。一旦輸入被耗盡，自動(dòng)機(jī)被稱(chēng)為“停止”了。
依賴(lài)自動(dòng)機(jī)停止時(shí)的狀態(tài)，稱(chēng)呼這個(gè)自動(dòng)機(jī)要么是“接受”要么“拒絕”這個(gè)輸入。如果停止于“接受狀態(tài)”，則自動(dòng)機(jī)“接受”了這個(gè)字。在另一方面，如果它停止于“拒絕狀態(tài)”，則這個(gè)字被“拒絕”。自動(dòng)機(jī)接受的所有字的集合被稱(chēng)為“這個(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)是被接受還是被拒絕。
一般的說(shuō)，自動(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è)度量是足夠的小。
術(shù)語(yǔ)釋義
自動(dòng)機(jī)有如下基本概念：
符號(hào) ：有某種意義或在這個(gè)機(jī)器上有效的任意數(shù)據(jù)(datum)。符號(hào)有時(shí)就叫做“字母”。
字：通過(guò)一些符號(hào)串接而形成的有限字符串。
字母表 ：符號(hào)的有限集合。字母表經(jīng)常指示為sigma ，它是在字母表中所有字母的集合。
語(yǔ)言 ：字的集合，由給頂字母表中的符號(hào)形成。可以是也可以不是無(wú)限的。
Kleene閉包 ：一個(gè)語(yǔ)言可以被認(rèn)為是所有可能字的子集。所有可能字的集合可以被認(rèn)為是所有可能的字符串串接的集合。形式上說(shuō)，所有可能字符串的集合叫做自由幺半群。它被指示為 Sigma *}，上標(biāo) * 被稱(chēng)為Kleene星號(hào)。
類(lèi)別
常見(jiàn)自動(dòng)機(jī)有以下幾種：以電話(huà)交換機(jī)為主要實(shí)例的有限自動(dòng)機(jī)，是自動(dòng)機(jī)理論的基礎(chǔ)，被應(yīng)用到自動(dòng)控制，生物系統(tǒng)中；由下推表組成的單項(xiàng)非確定程序的下推自動(dòng)機(jī)；線(xiàn)性有界自動(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ī)就接收它，如果不是，就不接收它。
自動(dòng)機(jī)可分為有限自動(dòng)機(jī)、后進(jìn)先出自動(dòng)機(jī)、線(xiàn)性有界自動(dòng)機(jī)、圖靈機(jī)等幾種。它們對(duì)語(yǔ)言的識(shí)別能力各不相同。
計(jì)算能力與判定問(wèn)題
確定有限狀態(tài)自動(dòng)機(jī)與非確定有限狀態(tài)自動(dòng)機(jī)識(shí)別的語(yǔ)言都是正則語(yǔ)言。由于正則語(yǔ)言的良好性質(zhì)，許多為其他自動(dòng)機(jī)（下推自動(dòng)機(jī)或圖靈機(jī)）不能判定的問(wèn)題，在有限狀態(tài)自動(dòng)機(jī)的情形下，都可以得到判定，并且存在有效的算法。
對(duì)一個(gè)確定有限狀態(tài)自動(dòng)機(jī)，下述判定問(wèn)題都可以判定，并且存在有效的算法。
該自動(dòng)機(jī)識(shí)別的語(yǔ)言是否為空集；
該自動(dòng)機(jī)識(shí)別的語(yǔ)言是否為有限集；
該自動(dòng)機(jī)是否與另一個(gè)確定有限狀態(tài)自動(dòng)機(jī)識(shí)別同一個(gè)的語(yǔ)言。
理論發(fā)展
美國(guó)語(yǔ)言學(xué)家N.諾姆·喬姆斯基等人建立了形式文法和自動(dòng)機(jī)之間的聯(lián)系，證明語(yǔ)言的形式文法與自動(dòng)機(jī)之間存在著如下的對(duì)應(yīng)關(guān)系：①若某一語(yǔ)言能用圖靈機(jī)來(lái)識(shí)別，則它就能用 O型文法生成，反之亦然；
②若某一語(yǔ)言能用線(xiàn)性有界自動(dòng)機(jī)來(lái)識(shí)別，則它就能用上下文敏感文法生成，反之亦然；
③若某一語(yǔ)言能用后進(jìn)先出自動(dòng)機(jī)來(lái)識(shí)別，則它就能用上下文自由文法生成，反之亦然；
④若某一語(yǔ)言能用有限自動(dòng)機(jī)來(lái)識(shí)別，則它就能用有限狀態(tài)文法生成，反之亦然。
這種關(guān)于形式文法與自動(dòng)機(jī)的關(guān)系，反映了語(yǔ)言的生成過(guò)程與識(shí)別過(guò)程的內(nèi)在聯(lián)系，它已成為計(jì)算機(jī)科學(xué)的基石之一。這是語(yǔ)言學(xué)對(duì)于現(xiàn)代自然科學(xué)發(fā)生影響的一個(gè)明證。
參考資料 >