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

劉 威

（大連海洋大學(xué)）

當(dāng)我們用計(jì)算機(jī)進(jìn)行問題的求解時(shí)，首先需要用適當(dāng)?shù)臄?shù)據(jù)進(jìn)行問題表示，然后再設(shè)計(jì)相應(yīng)的算法對這些數(shù)據(jù)進(jìn)行變換處理來獲得問題的求解結(jié)果。因此，對問題進(jìn)行建模和形式化表示，然后進(jìn)行處理是進(jìn)行計(jì)算機(jī)求解的基本途徑。數(shù)理邏輯、自動(dòng)機(jī)理論給出了如何描述一些基本問題以及如何建立問題的抽象表示，并通過對這些抽象化的表示的性質(zhì)和它的變化方法進(jìn)行研究。這些模型都是問題數(shù)學(xué)模型的典范，給計(jì)算機(jī)問題求解提供了堅(jiān)實(shí)的理論基礎(chǔ)，是計(jì)算機(jī)求解問題的重要方法和思想。

計(jì)算機(jī)科學(xué)與技術(shù)學(xué)科是以數(shù)學(xué)和電子學(xué)科為基礎(chǔ)發(fā)展起來的，一方面研究計(jì)算機(jī)領(lǐng)域中的一些普遍規(guī)律，描述計(jì)算的基本概念與模型，其重點(diǎn)是描述現(xiàn)象、解釋規(guī)律。另一方面是包括計(jì)算機(jī)硬件、軟件的計(jì)算機(jī)系統(tǒng)設(shè)計(jì)和實(shí)現(xiàn)的工程技術(shù)，簡單地說，計(jì)算機(jī)科學(xué)與技術(shù)學(xué)科通過在計(jì)算機(jī)上建立模型并模擬物理過程來進(jìn)行科學(xué)調(diào)查和研究，它系統(tǒng)地研究信息描述和變換算法，主要包括信息描述和變換算法的理論、分析、效率、實(shí)現(xiàn)和應(yīng)用。

所有問題的描述都要以計(jì)算機(jī)能識別的語言來實(shí)現(xiàn)，計(jì)算機(jī)語言的文法描述提供了生成語言的手段，但是，對于語言句子的識別來說，我們需要一些識別語言的模型，我們可以稱這種模型為語言的識別模型。這種識別模型應(yīng)該滿足必要的約束條件，首先模型具有有窮個(gè)狀態(tài)，不同的狀態(tài)代表不同的意義。按照實(shí)際的需要，模型可以在不同的狀態(tài)下完成特定語言的識別。我們可以將輸入數(shù)據(jù)中出現(xiàn)的符號組成一個(gè)字符的列表。模型將輸入數(shù)據(jù)作為線性表來進(jìn)行處理和變換。模型有一個(gè)初始的狀態(tài)，它是系統(tǒng)的開始狀態(tài)，系統(tǒng)在這個(gè)狀態(tài)下開始進(jìn)行問題的求解。模型中還有一些狀態(tài)表示它到目前為止所讀入的字符構(gòu)成的字符串是模型從開始狀態(tài)引導(dǎo)到這種狀態(tài)的所有字符串構(gòu)成的語言就是模型所能識別的輸入。我們可以將此模型對應(yīng)成有窮狀態(tài)自動(dòng)機(jī)的物理模型，在處理問題的時(shí)候，它可以接受一個(gè)關(guān)于問題的輸入數(shù)據(jù)，數(shù)據(jù)以字符串的形式提供，我們把這些輸入數(shù)據(jù)劃分成一系列的小部分，每個(gè)部分由若干字符組成，為了不讓輸入數(shù)據(jù)量影響該模型對問題的處理，我們約定，輸入數(shù)據(jù)從開始輸入時(shí)的時(shí)間點(diǎn)開始處理，輸入狀態(tài)可以是無窮的，這就是說，從輸入第一部分?jǐn)?shù)據(jù)開始，輸入端可以有任意長度的輸入序列。而且，模型有一個(gè)有窮狀態(tài)控制器，該控制器的狀態(tài)只有有窮多個(gè)，并且規(guī)定，模型的每一個(gè)動(dòng)作分為三步，讀入待輸入的字符，根據(jù)當(dāng)前的狀態(tài)和讀入的字符改變有窮控制器的狀態(tài)，讀下一部分輸入數(shù)據(jù)。計(jì)算機(jī)的各個(gè)組成部分，既包括硬件系統(tǒng)也包括軟件系統(tǒng)，都可以對其進(jìn)行形式化的定義，計(jì)算機(jī)的硬件系統(tǒng)包括中央處理器、存儲(chǔ)器、外部設(shè)備，可以形式化地用一個(gè)三元組來描述，對計(jì)算機(jī)個(gè)各個(gè)硬件部分進(jìn)行管理的軟件的功能也可以用形式化的方法來描述，例如，操作系統(tǒng)的各個(gè)功能模塊、處理器管理、線程調(diào)度、文件系統(tǒng)、設(shè)備驅(qū)動(dòng)程序、網(wǎng)絡(luò)通信管理、虛擬內(nèi)存管理等都可以進(jìn)行形式化的定義。有窮狀態(tài)機(jī)就是進(jìn)行這種形式化定義的模型，有窮狀態(tài)機(jī)是一個(gè)五元組，分別是描述狀態(tài)的有窮非空集合，它稱為有窮狀態(tài)機(jī)的一個(gè)狀態(tài)，輸入符號表，所有輸入有窮狀態(tài)機(jī)的關(guān)于問題的描述都是這個(gè)符號表中的符號組成的字符串。狀態(tài)轉(zhuǎn)換函數(shù)，表示有窮狀態(tài)自動(dòng)機(jī)在某一狀態(tài)讀入字符，將狀態(tài)變成另外一種狀態(tài)，有窮狀態(tài)自動(dòng)機(jī)一定有一個(gè)初始狀態(tài)，接受輸入后，從這個(gè)初始狀態(tài)出發(fā)，進(jìn)行一系列的狀態(tài)轉(zhuǎn)換，然后到達(dá)一個(gè)終止?fàn)顟B(tài)，即問題求解結(jié)束。對于每個(gè)問題的輸入，有窮狀態(tài)自動(dòng)機(jī)都會(huì)進(jìn)行一系列的狀態(tài)轉(zhuǎn)換，這個(gè)轉(zhuǎn)換的過程，可以用一系列不同的狀態(tài)來表述，這個(gè)過程就是有窮自動(dòng)機(jī)的主體框架，如果某個(gè)先前引入的狀態(tài)發(fā)現(xiàn)輸入串肯定不是語言的句子，就進(jìn)入此狀態(tài)，完成對輸入狀態(tài)的剩余部分的輸入，即進(jìn)行相應(yīng)的例外處理，狀態(tài)機(jī)的狀態(tài)具有一定的記憶功能，不同的狀態(tài)對應(yīng)不同的情況。由于有窮狀態(tài)機(jī)只有有窮個(gè)狀態(tài)，所以在識別一個(gè)輸入的過程中，如果有無窮種情況需要記憶，我們肯定是無法構(gòu)造出相應(yīng)的有窮狀態(tài)自動(dòng)機(jī)的，對應(yīng)輸入的每一個(gè)變換步驟都有一個(gè)狀態(tài)與之對應(yīng)，有窮狀態(tài)機(jī)在任意時(shí)刻可以處于有窮多個(gè)狀態(tài)，有事狀態(tài)是有窮的，我們可以認(rèn)為這種有窮狀態(tài)自動(dòng)機(jī)的一個(gè)狀態(tài)對應(yīng)的是先前定義的有窮狀態(tài)自動(dòng)機(jī)的一個(gè)狀態(tài)集合。實(shí)際上我們可以認(rèn)為這種有窮狀態(tài)自動(dòng)機(jī)具有智能，在一個(gè)狀態(tài)下，它可以根據(jù)當(dāng)前從輸入字符串讀入的字符自動(dòng)的在集合中選擇一個(gè)進(jìn)入正確的狀態(tài)。在這種前提下，只要在有窮狀態(tài)自動(dòng)機(jī)中存在一條從開始狀態(tài)出發(fā)，最終到達(dá)某一個(gè)終止?fàn)顟B(tài)的路徑，那么，就認(rèn)為它接受了串，否則認(rèn)為它不接受串。前面定義的有窮狀態(tài)自動(dòng)機(jī)有一個(gè)很大的限制，對一個(gè)輸入的字符串，它只是輸出此串是合法串還是不合法串的結(jié)論。這在很多時(shí)候是不夠的，因?yàn)槲覀冇袝r(shí)不僅希望系統(tǒng)能得出一個(gè)輸入串是否為要求串的結(jié)論，我們更希望系統(tǒng)在處理此串的過程中給出必要的處理步驟，因此，從抽象的角度考慮，已經(jīng)沒有必要再設(shè)置終止?fàn)顟B(tài)集。我們可以由此得出，有窮狀態(tài)自動(dòng)機(jī)具有有窮的存儲(chǔ)功能，而且允許直接根據(jù)當(dāng)前狀態(tài)變換到新的狀態(tài)。有窮狀態(tài)自動(dòng)機(jī)可以作為一種識別模型，分別按照對推導(dǎo)和規(guī)約的模擬。

計(jì)算機(jī)學(xué)科研究的是什么樣的問題能夠被有效的自動(dòng)化，而實(shí)現(xiàn)問題有效自動(dòng)化的基礎(chǔ)首先是實(shí)現(xiàn)對問題的恰當(dāng)?shù)男问交枋觥Ｓ懈F狀態(tài)自動(dòng)機(jī)就是這樣的一種形式化的描述模型。有窮狀態(tài)自動(dòng)機(jī)擅長語言的識別，使得人們更容易理解和使用它，而適應(yīng)計(jì)算機(jī)的表示形式又使得我們能更容易使用計(jì)算機(jī)系統(tǒng)處理語言。

王茁.基于有限狀態(tài)自動(dòng)機(jī)的公共交到站時(shí)間預(yù)測模型［D］.哈爾濱工業(yè)大學(xué)，2012.