劉 威

（大連海洋大學）

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

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

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

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

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