-
有限狀態自動機
鎖定
- 中文名
- 有限狀態自動機
- 外文名
- finite state machine
- 研究對象
- 自動機理論
- 識別語言
- 正規語言
有限狀態自動機主要特點
有限狀態自動機是具有離散輸入和輸出的系統的一種數學模型。
其主要特點有以下幾個方面：
– (1)系統具有有限個狀態，不同的狀態代表不同的意義。按照實際的需要，系統可以在不同的狀態下完成規定的任務。
– (2)我們可以將輸入字符串中出現的字符彙集在一起構成一個字母表。系統處理的所有字符串都是這個字母表上的字符串。
– (3)系統在任何一個狀態下，從輸入字符串中讀入一個字符，根據當前狀態和讀入的這個字符轉到新的狀態。
– (4)系統中有一個狀態，它是系統的開始狀態。
– (5)系統中還有一些狀態表示它到目前為止所讀入的字符構成的字符串是語言的一個句子。
形式定義
· 定義：有限狀態自動機(FA—finite automaton)是一個五元組：
– M=(Q, Σ, δ, q0, F)
· 其中，
– Q——狀態的非空有窮集合。∀q∈Q，q稱為M的一個狀態。
– Σ——輸入字母表。
– δ——狀態轉移函數，有時又叫作狀態轉換函數或者移動函數，δ：Q×Σ→Q，δ(q,a)=p。
– q0——M的開始狀態，也可叫作初始狀態或啓動狀態。q0∈Q。
– F——M的終止狀態集合。F被Q包含。任給q∈F，q稱為M的終止狀態。
有限狀態自動機類型
有多種類型的有限狀態自動機：接受器判斷是否接受輸入；轉換器對給定輸入產生一個輸出。常見的轉換器有 Moore 機 與 Mealy 機。Moore 機對每一個狀態都附加有輸出動作，Mealy 機對每一個轉移都附加有輸出動作。
有限狀態自動機還可以分成確定與非確定兩種。非確定有限狀態自動機可以轉化為確定有限狀態自動機。
有限狀態自動機識別的語言是正規語言。
有限狀態自動機除了它在理論上的價值，還在數字電路設計、詞法分析、文本編輯器程序等領域得到了應用。
自動機接受的所有字串構成了自動機識別的語言 L(M)。
非確定有限狀態自動機
一個非確定有限狀態自動機（NFA "Non-deterministic finite automaton"）M 是由下述元素構成的五元組 (Q,Σ,δ,q0,F)
有窮狀態集合 Q ；
有窮輸入字母表 Σ；
轉移函數 δ: Q × Σ -> 2Q；
初始狀態 q0；
終結狀態集合 F，F 包含於 Q 。
自動機從初始狀態 q0 起，逐一讀入輸入串（由輸入字母表 Σ 的字母構成）的每一個字母，根據當前狀態、輸入字母和轉移函數 δ 決定自動機的下一步狀態；如果輸入串結束時，自動機處於終結狀態集合 F 的某一個狀態，這表示自動機接受該字串；否則自動機不接受該字串。
非確定有限狀態自動機與確定有限狀態自動機的唯一區別是它們的轉移函數不同。確定有限狀態自動機對每一個可能的輸入只有一個狀態的轉移。非確定有限狀態自動機對每一個可能的輸入可以有多個狀態轉移，接受到輸入時從這多個狀態轉移中非確定地選擇一個。
自動機接受的所有字串構成了自動機識別的語言 L(M)。
有限狀態自動機計算能力
確定有限狀態自動機與非確定有限狀態自動機識別的語言都是正則語言。由於正則語言的良好性質，許多為其他自動機（下推自動機或圖靈機）不能判定的問題，在有限狀態自動機的情形下，都可以得到判定，並且存在有效的算法。
對一個確定有限狀態自動機，下述判定問題都可以判定，並且存在有效的算法。
該自動機識別的語言是否為空集。
該自動機識別的語言是否為有限集。
該自動機是否與另一個確定有限狀態自動機識別同一個的語言。
例如：有限狀態自動機：輸入串為3進制數，輸出為模5的餘數（0，1，2，3，4）
模5的餘數總共只有5個，這就是5個狀態。初始狀態為0，每個狀態也都是最終狀態。
三進制每位數有3種可能，因此每種狀態有3種躍遷可能。
把3進制串理解成從高位到低位一個一個輸入，每條輸入就是一次躍遷，狀態就是到當前輸入為止的3進制數模5的餘數。
躍遷的函數如下：
目標狀態 = （當前狀態 *進制數(此題為3) + 串的當前位）% 5。
舉例如下：
三進制數 12112
當前狀態 輸入 躍遷
0(start) 1 (0*3+1) % 5 = 1
1 2 (1*3+2) % 5 = 0
0 1 (0*3+1) % 5 = 1
1 1 (1*3+1) % 5 = 4
4 2 (4*3+2) % 5 = 4 (最終結果)
</CA>
有限狀態自動機最小化
根據 Myhill-Nerode 定理，在同構意義下接受一個正則語言的最少狀態的確定有限狀態自動機是唯一的。同時我們還存在有效的算法（時間開銷是O(n^2)的）構造出與給定確定有限狀態自動機等價的最小化的確定有限狀態自動機。
