-
確定有限狀態自動機
鎖定
- 中文名
- 確定有限狀態自動機
- 外文名
- deterministic finite automation
- 縮 寫
- DFA
- 領 域
- 計算機
確定有限狀態自動機基礎概念
確定有限狀態自動機定義
確定有限狀態自動機
是由
一個非空有限的狀態集合
；
一個開始狀態
；
一個接受狀態的集合
；
確定有限狀態自動機工作方式（非正式的語義）
確定有限狀態自動機從起始狀態開始，一個字符接一個字符地讀入一個字符串
（這裏的
指示Kleene星號算子。），並根據給定的轉移函數一步一步地轉移至下一個狀態。在讀完該字符串後，如果該自動機停在一個屬於F的接受狀態，那麼它就接受該字符串，反之則拒絕該字符串。
[1]
確定有限狀態自動機擴展轉移函數
為了在保證嚴謹的前提下，方便地敍述關於DFA的內容，我們定義如下擴展的轉移函數：
確定有限狀態自動機工作方式（正式的語義）
對於一個確定有限狀態自動機
，如果
，我們就説該自動機接受字符串w，反之則表明該自動機拒絕字符串w。
確定有限狀態自動機DFA與有向圖
除了數學上的嚴謹表述，通常為了討論方便，也使用狀態圖直觀地表示DFA。不難發現，對於一個給定的DFA，存在唯一一個對應的有向圖（但是嚴格意義上一個有向圖不能確定出唯一一個DFA）。有向圖的每個結點對應一個狀態，每條有向邊對應一種轉移。習慣上將結點畫成兩個圈表示接受狀態，一個圈表示拒絕狀態。用一條沒有起點的邊指向起始狀態。
確定有限狀態自動機利弊
DFA是一種實際的計算模型，因為有平凡的線性時間、恆定空間的在線算法模擬在輸入流上的DFA。給定兩個DFA有有效算法找到識別它們所識別語言的並集、交集和補集的DFA。還有有效算法確定一個DFA是否接受任何給定字符串，一個DFA是否接受所有字符串，兩個DFA是否識別同樣的語言，和對特定正則語言找到狀態數目最小的DFA（最小DFA）。
在另一方面，DFA在可識別的語言上有嚴格的限制—很多簡單的語言，包括需要多於恆定空間來解決的任何問題，不能被DFA識別。經典的DFA不能識別的簡單語言的例子是括號語言，就是由正確配對的括號組成的語言，比如 (()())。由形如ab的字符串組成的語言，就是有限數目個a，隨後是相等數目個b。可以證明沒有DFA有足夠狀態來識別這種語言（通俗地説，因為需要至少2n個狀態，而n是不恆定的）。
[1]
確定有限狀態自動機其他
- 能被確定有限狀態自動機識別的語言是正則語言。
- 確定有限狀態自動機是非確定有限狀態自動機的一種極限形式。
- 確定有限狀態自動機在計算能力上等價於非確定有限狀態自動機。
確定有限狀態自動機封閉性及一些運算
確定有限狀態自動機封閉性
確定有限狀態自動機補運算
確定有限狀態自動機交運算和並運算
有兩個DFA，
和
，那麼由這兩個DFA創造出來的新的自動機定義為：
。其中
，
為
的開始狀態，
為
的轉移函數，且作如下定義：
。
當
時，由上述方法得到的
就是DFA
和
的交運算，記作
。也就是説對於讀入的字符串w，當且僅當
和
同時接受w的時候
接受w。
當
時，由上述方法得到的
就是DFA
和
的並運算，記作：
。也就是説對於讀入的字符串w，只要
或
中至少有一個接受w，
就接受w。
確定有限狀態自動機同態和逆同態運算
一個同態函數
可以遞歸的定義為：
於是則有
。（以上所述中
為空字符，
）
確定有限狀態自動機最小自動機
確定有限狀態自動機等價類自動機
對於一個正則語言，接受該語言的等價類自動機是一個
的5-元組。其定義如下：
Q是等價關係~L的等價類的集合：
的集合
確定有限狀態自動機唯一性
對於任意給定的確定有限狀態自動機都能找到一個與之計算能力等價的最小確定有限狀態自動機，簡稱最小自動機。該最小自動機中狀態的數量等於能識別相同語言的等價類自動機中等價關係的數量，我們可以稱最小自動機和等價類自動機“實際上”是相等的，也就是同構。非正式的説法是：對於最小自動機上的任意狀態都可以通過一個同構函數變換成等價類自動機上的一個狀態。
確定有限狀態自動機算法
定義一個非等價關係：
，如下步驟可以得到這個集合N：
1.
如果，就給所有的狀態對(p,q)和(q,p)打上標記
2.重複步驟3，直到所標記的狀態對沒有變化為止
3.對於未標記的狀態對(p,q)和σ，如果
被標記過了就把(p,q)也標記上
4.以上所有標記了的狀態對的集合就是非等價關係N
以下是由一個任意DFA轉換到一個最小DFA的步驟：
- 把所有不能從開始狀態達到的狀態刪除
- 通過上述標記算法計算非等價關係N
- 一步一步將不屬於N的狀態對中的兩個狀態合成一個狀態
- 詞條統計
-
- 瀏覽次數：次
- 編輯次數：2次歷史版本
- 最近更新： w_ou