有限狀態(tài)自動(dòng)機(jī)

1、有限狀態(tài)自動(dòng)機(jī)Automatona machine without feelings引言計(jì)算機(jī)很重要的一個(gè)任務(wù)就是理解用戶的輸入信息，并進(jìn)行相應(yīng)的處理輸入信息的形式可能是多種多樣的敲擊鍵盤點(diǎn)擊按鈕動(dòng)作手勢(shì)有一種簡(jiǎn)單而有效的處理方法是有限狀態(tài)自動(dòng)機(jī)（finite state automaton）2概要這一章我們將介紹有關(guān)有限狀態(tài)自動(dòng)機(jī)的基本知識(shí)背景形式定義構(gòu)造方式應(yīng)用示例3有限狀態(tài)自動(dòng)機(jī)計(jì)算機(jī)程序通常要處理一系列的符號(hào)，例如文檔、網(wǎng)頁中的字母或詞語，甚至包括另一個(gè)計(jì)算機(jī)程序中的文本計(jì)算機(jī)科學(xué)家們常常使用一種稱為有限狀態(tài)自動(dòng)機(jī)（FSA）的流程圖來處理這些輸入盡管這些流程圖非常簡(jiǎn)單，它們卻能適用于許

2、多問題，不僅能處理輸入的文本信息，還能設(shè)計(jì)計(jì)算機(jī)界面和尋找圖像規(guī)律4尋寶游戲我們將通過一個(gè)游戲來學(xué)習(xí)有關(guān)有限狀態(tài)自動(dòng)機(jī)的概念和知識(shí)你既可以和幾個(gè)伙伴一起來玩這個(gè)游戲（參見視頻），也可以自己一個(gè)人來玩（使用卡片）準(zhǔn)備好了么？開始我們的金銀島冒險(xiǎn)之旅吧5尋寶游戲設(shè)想一下你現(xiàn)在處于只有島嶼的世界，海盜船來往于不同的島嶼之間幸運(yùn)的是，海盜們都非常友善，而且樂于讓旅行的人“搭便船”每個(gè)島嶼配備了兩艘船A和B，你可以任選其一開始你的旅途每當(dāng)你到達(dá)一個(gè)島嶼，你都能再選一艘船A或B，但不能同時(shí)選兩個(gè)6尋寶游戲比如，在下面的小地圖中，如果你從海盜島啟程，搭乘船A，你將會(huì)抵達(dá)船難灣；如果你再次搭乘船A，你將會(huì)回到

3、海盜島7尋寶游戲現(xiàn)在我們換一張有7座島嶼的地圖，你的目標(biāo)是找到從海盜島到金銀島的路線唯一的問題是，地圖上并沒有標(biāo)出箭頭，你需要自己去探索旅行的路線為了達(dá)成這個(gè)目標(biāo)，你可以問每座島上的A船或B船各駛向哪里后面我們將具體解釋如何進(jìn)行這個(gè)游戲，從而了解自動(dòng)機(jī)的構(gòu)造形式8島嶼地圖9尋寶游戲請(qǐng)將以下形式的卡片對(duì)折，讓沒有目的地信息的一面向上，這樣你只能在到達(dá)某個(gè)島嶼之后，才能“詢問”島嶼的每艘船的目的地只需將卡片翻過來即可10尋寶游戲首先請(qǐng)準(zhǔn)備一張如前面所示的空白的藏寶圖，選擇A船或者B船從海盜島啟程在到達(dá)下一個(gè)島嶼前，在地圖上畫上箭頭并做好標(biāo)簽，因?yàn)檫^一會(huì)兒你可能會(huì)又回到這個(gè)島嶼，這樣就能記起上一次你

4、選擇的路線，避免重復(fù)持續(xù)這個(gè)過程，相信你很快就會(huì)找到金銀島了，加油！11實(shí)踐與思考你能找到通往金銀島的路線么？請(qǐng)標(biāo)記好你在地圖上發(fā)現(xiàn)的路線當(dāng)你完成了整幅地圖之后，能指出去金銀島的最短航線么？你能找到包含有回路（即循環(huán)訪問某些島嶼一次以上的）并能最終抵達(dá)金銀島的航線么？12路線藏寶圖13有限狀態(tài)自動(dòng)機(jī)經(jīng)過這個(gè)游戲，我們對(duì)有限狀態(tài)自動(dòng)機(jī)已經(jīng)有了初步的認(rèn)識(shí)游戲中的每一次航行，都只取決于你當(dāng)前所在的島嶼以及你所選擇的船只島嶼即表示自動(dòng)機(jī)的狀態(tài)，船只即表示自動(dòng)機(jī)的輸入生活中的許多場(chǎng)景，也許你未曾留意，但實(shí)際上都是有限狀態(tài)自動(dòng)機(jī)的模式14生活中的自動(dòng)機(jī)當(dāng)你去銀行的自動(dòng)提款機(jī)上取現(xiàn)金時(shí)，這臺(tái)機(jī)器的計(jì)算機(jī)程序

5、將指示你的操作在這個(gè)程序中，所有可能的用戶操作都被保存成為有限狀態(tài)自動(dòng)機(jī)的形式你每按一個(gè)按鈕，有限狀態(tài)自動(dòng)機(jī)便自動(dòng)將你導(dǎo)向圖中的另一座“島嶼”這些“島嶼”在計(jì)算機(jī)中有相應(yīng)的提示，比如“提取100元現(xiàn)金”，“打印回條”或者“取出您的磁卡”15自動(dòng)機(jī)的表示計(jì)算機(jī)科學(xué)家們使用圓圈來表示每座島嶼，用箭頭指示移動(dòng)的方向，從而用有限狀態(tài)自動(dòng)機(jī)的形式畫出尋寶地圖16自動(dòng)機(jī)的表示在上圖中，最終藏有寶藏的島嶼用雙線圓圈表示，最開始出發(fā)的島嶼由沒有標(biāo)記的箭頭指示（數(shù)字1）用自動(dòng)機(jī)的術(shù)語來說，一個(gè)島嶼被稱為一個(gè)狀態(tài)（state），“金銀島”則被稱為終結(jié)狀態(tài)（accept state）之所以稱為狀態(tài)是因?yàn)樗f明了在有

6、了之前的輸入后（輸入A或輸入B），你進(jìn)入了自動(dòng)機(jī)過程中哪一個(gè)階段的結(jié)果17自動(dòng)機(jī)的表示如果某個(gè)輸入的序列（例如BBAB），能夠從初始狀態(tài)，經(jīng)過狀態(tài)轉(zhuǎn)移之后，到達(dá)“終結(jié)狀態(tài)”，則說明這一輸入是“可接受的”（acceptable）在我們的例子中，“可接受”表示這是一條正確的尋寶路線（并不一定是最短最好的），在其他自動(dòng)機(jī)的應(yīng)用中，接受狀態(tài)可能有更具體的含義，如檢查輸入是否構(gòu)成有效的命令序列18有限狀態(tài)自動(dòng)機(jī)至此，我們對(duì)于“有限狀態(tài)自動(dòng)機(jī)”這個(gè)聽起來很復(fù)雜的名字，終于可以明確其意義了“有限”（finite）是指在邏輯圖中有有限數(shù)量的狀態(tài)（如島）“狀態(tài)”（state）是游戲中島嶼的別稱“自動(dòng)機(jī)”（aut

7、omaton）是指能遵循簡(jiǎn)單規(guī)則自主運(yùn)行的機(jī)器，即根據(jù)當(dāng)前狀態(tài)和輸入決定所轉(zhuǎn)移的下一個(gè)狀態(tài)的機(jī)制19實(shí)踐與思考在表示自動(dòng)機(jī)的圖（a）中，下面哪些輸入能被接受ABBABAAABBBAAAABABAAAABA的共同點(diǎn)么？20實(shí)踐與思考（作業(yè)）在表示自動(dòng)機(jī)的圖（b）中，下面哪些輸入能被接受ABBAABABAABBABABAABBA能描述出被圖（b）接受的指令的共同點(diǎn)么？21實(shí)踐與思考在表示自動(dòng)機(jī)的圖（c）中，下面哪些輸入能被接受BBBBBBAABBAAAA能描述出被圖（c）接受的指令的共同點(diǎn)么？22自動(dòng)機(jī)的形式定義23自動(dòng)機(jī)的形式定義你能把這些自動(dòng)機(jī)表示成五元組的形式么24自動(dòng)機(jī)的應(yīng)用一些使用FSA

8、的計(jì)算機(jī)程序?qū)ｉT用于處理文本中的句子，它們既可以自己造句，也可以處理用于輸入的句子25自動(dòng)機(jī)的應(yīng)用使用如上圖所示的自動(dòng)機(jī)，選擇狀態(tài)圖上任意的路徑并記錄得到的單詞，便可以構(gòu)造合法的句子同樣，這個(gè)自動(dòng)機(jī)也可以用來由識(shí)別用戶輸入的句子，檢查其是否符合特定的“模式”試著自己設(shè)計(jì)一個(gè)能造句的FSA，并讓其他人使用你的FSA來造句26識(shí)別美元的自動(dòng)機(jī)27識(shí)別派生詞的自動(dòng)機(jī)28進(jìn)階討論非確定有限狀態(tài)自動(dòng)機(jī)我們前面介紹的，都屬于確定型的有限狀態(tài)自動(dòng)機(jī)（Deterministic Finite Automation, DFA）與之相對(duì)應(yīng)的還有非確定型的有限狀態(tài)自動(dòng)機(jī)（Nondeterministic Finit

9、e Automata, NFA）這里是所說的“確定”，主要指的是狀態(tài)轉(zhuǎn)移函數(shù)，非確定意味著在某個(gè)狀態(tài)的相同輸入下可能會(huì)有不同的轉(zhuǎn)移狀態(tài)30非確定有限狀態(tài)自動(dòng)機(jī)從狀態(tài)圖模型的角度考慮，NFA可以認(rèn)為是允許從一個(gè)狀態(tài)引申出去的兩個(gè)箭頭擁有同一個(gè)標(biāo)記31NFA的形式定義32非確定有限狀態(tài)自動(dòng)機(jī)在這種情況下，對(duì)于同一個(gè)輸入序列，自動(dòng)機(jī)可能會(huì)有多條不同的轉(zhuǎn)移路徑，此時(shí)只需有一條路徑最終到達(dá)終結(jié)狀態(tài)，即認(rèn)為該輸入是可接受的由于這樣的特性，非確定有限狀態(tài)自動(dòng)機(jī)具有更好的靈活性，往往能用較少的狀態(tài)來表示相同的可接受輸入集合同時(shí)，在許多問題當(dāng)中，它的構(gòu)造形式也更符合人的直觀思維33非確定有限狀態(tài)自動(dòng)機(jī)但是，非確

10、定機(jī)也就意味著狀態(tài)轉(zhuǎn)移不再是唯一的了，這使得我們?cè)谟糜?jì)算機(jī)實(shí)現(xiàn)時(shí)遇到了困難（還記得算法的定義么？）幸運(yùn)的是，我們可以通過一定的轉(zhuǎn)換規(guī)則，將非確定自動(dòng)機(jī)變化為確定型的有限狀態(tài)自動(dòng)機(jī)，這個(gè)過程稱為自動(dòng)機(jī)的確定化一般的，我們可以先構(gòu)造非確定型的有限狀態(tài)自動(dòng)機(jī)，再將其確定化以滿足需要34具有輸出的有限自動(dòng)機(jī)前面涉及的有限狀態(tài)自動(dòng)機(jī)，都是用于對(duì)字母表上的輸入序列進(jìn)行識(shí)別，返回“接受”或者“拒絕”兩種信息之一現(xiàn)實(shí)生活中還有一種有限狀態(tài)自動(dòng)機(jī)，對(duì)于不同的輸入序列，除內(nèi)部狀態(tài)不斷改變外，還不斷向系統(tǒng)外部輸出各種信號(hào)就像我們前面提到過的銀行ATM系統(tǒng)，會(huì)在你不同的操作過程中返回相應(yīng)的提示信息35具有輸出的有限自

11、動(dòng)機(jī)具有輸出的有限狀態(tài)自動(dòng)機(jī)，一般沒有終結(jié)狀態(tài)集，不存在“接受”或者“拒絕”輸入序列的問題在讀入輸入串的過程中，自動(dòng)機(jī)的狀態(tài)不斷改變，并且在每個(gè)狀態(tài)上都有輸出一般的有限狀態(tài)自動(dòng)機(jī)可以看作只有0、1兩種輸出的自動(dòng)機(jī)：終結(jié)狀態(tài)輸出1，非終結(jié)狀態(tài)輸出036具有輸出的有限自動(dòng)機(jī)根據(jù)輸出機(jī)制的不同，具有輸出的有限自動(dòng)機(jī)又可以分為摩爾（Moore）機(jī)和米利（Mealy）機(jī)兩種摩爾機(jī)的輸出只與自動(dòng)機(jī)當(dāng)前所處的狀態(tài)有關(guān)米利機(jī)的輸出與自動(dòng)機(jī)當(dāng)前所處的狀態(tài)以及面臨的輸入有關(guān)37摩爾機(jī)的形式定義38米利機(jī)的形式定義39自動(dòng)機(jī)與正則表達(dá)式正則表達(dá)式是在計(jì)算機(jī)當(dāng)中很常見的一種表示方法，常常用于描述和匹配符合特定規(guī)則的字

12、符串正則表達(dá)式的定義十分簡(jiǎn)單，通過字符表中的元字符，只使用連接、并集和閉包三種運(yùn)算在許多著名的文本編輯器和集成環(huán)境當(dāng)中，如vi、grep、Editplus等等，都提供了對(duì)正則表達(dá)式的支持40自動(dòng)機(jī)與正則表達(dá)式大家可能最為熟悉的文本處理器應(yīng)當(dāng)是MS Word，還記得當(dāng)中的“?”以及“*”的作用么？它們就是正則表達(dá)式！正則表達(dá)式與有限狀態(tài)自動(dòng)機(jī)是完全等價(jià)的，可以相互轉(zhuǎn)換，有興趣的同學(xué)請(qǐng)自學(xué)相關(guān)的知識(shí)，試試用正則表達(dá)式描述前面那三個(gè)自動(dòng)機(jī)所表示的序列41參考資料更多關(guān)于自動(dòng)機(jī)的內(nèi)容，例如怎樣確定化NFA，正則表達(dá)式與自動(dòng)機(jī)如何轉(zhuǎn)化，可以參考以下的文獻(xiàn)自動(dòng)機(jī)理論、語言和計(jì)算導(dǎo)論形式語言與自動(dòng)機(jī)理論編譯原理42無處不在的自動(dòng)機(jī)自動(dòng)機(jī)對(duì)我們生活的影響力之大可能會(huì)超出你的想象，它的應(yīng)用場(chǎng)景可以說是無處不在的BBS信息監(jiān)測(cè)系統(tǒng)自動(dòng)售貨機(jī)圖像壓縮和圖像增強(qiáng)網(wǎng)絡(luò)入侵檢測(cè)信息爆發(fā)度檢測(cè)XML文本匹配43無處不在的自動(dòng)機(jī)世界上最龐大的、無數(shù)人每天都會(huì)用到的自動(dòng)機(jī)是什么？那就是我們使用的萬維網(wǎng)每個(gè)網(wǎng)頁就好比一座島嶼