有限狀態自動機模型

劉 威

（大連海洋大學）

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

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

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

計算機學科研究的是什么樣的問題能夠被有效的自動化，而實現問題有效自動化的基礎首先是實現對問題的恰當的形式化描述。有窮狀態自動機就是這樣的一種形式化的描述模型。有窮狀態自動機擅長語言的識別，使得人們更容易理解和使用它，而適應計算機的表示形式又使得我們能更容易使用計算機系統處理語言。

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