資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究非確定有限自動機可以轉換為確定有限自動機嗎？
是的，我們可以將 NFA 轉換為 DFA。對於每個 NFA，都存在一個等價的 DFA。等價性是根據語言接受來定義的。由於 NFA 不過是在輸入符號上允許零個、一個或多個轉換的有限自動機。它始終可以構建有限自動機，該自動機將並行模擬 DFA 在特定輸入符號上的所有移動，然後得到一個有限自動機，在該自動機中，每個輸入符號上都將恰好有一個轉換。在這裡，對應於 NFA，存在一個 DFA。為了構造等價於 NFA 的 DFA，應該記住 DFA 的狀態是 NFA 狀態的集合。
演算法 NFA – 到 – DFA
輸入 − NFA，狀態集 N = {n0,n1……nn}，起始狀態 n0。
輸出 − DFA，狀態集 D′={d0,d1,d2……dn}，起始狀態 d0。
d0=ε−closure (n0)
D′={d0}
將 d0 設定為未標記
while there is an unmarked state d in D′. {
set d marked {
For each input symbol 'a' {
Let T be a set of states in NFA to which there is a transition on 'a' from some state ni in d d′=ε−closure (T).
If d′ is not already present in D′ {
D′=D′∪{d′}
Add transition d→d′,labeled 'a'
set d′ unmarked
}
}
}
}示例 − 為以下 LEX 程式設計詞法分析器。
AUXILIARY DEFINITION S
letter = A|B|C|…….|Z
digit = 0 |1|2|………|9
TRANSLATION RULES
begin {return 1}
end {return 2}
If {return 3}
then {return 4}
else {return 5}
letter (letter+digit)* {value=Install ( );return 6}
digit + {value=Install ( );return 7}
< {value=1;return 8}
<= {value=2;return 8}
= {value=3;return 8}
< > {value=4;return 8}
> {value=5;return 8}
>= {value=6;return 8}解決方案
- 各種模式的組合 NFA 將是
- 將 NFA 轉換為 DFA − 對應的 DFA 將是。
狀態 {0, 1, 7, 11, 14, 19, 24, 26, 28, 30, 33, 35, 38, 40} 被組合並命名為 q0 以建立 DFA 的起始狀態。
在組合的 NFA 中，從狀態 1 到 2 和從狀態 24 到 25 的轉換是相同的，因為輸入“b”是一個字母。
狀態 2、25 被組合。類似地，其他狀態也被組合。
狀態 29、31 和 36 被組合，因為它們都在獲得輸入“<”後到達。
類似地，其他狀態也被組合。
更新於: 2021年10月26日
1K+ 次瀏覽
廣告