NFA構造DFA的子集算法
n 輸入：一個NFA N
n 輸出：一個DFA D
n 方法：為D構造一個轉換表Dtran。D的每一個狀態是一組NFA狀態的集合。以下是一些構造需要用到的函數。
|
操作
|
描述
|
|
ε-closure(s)
|
能夠從NFA的狀態s開始只通過ε轉換到達的NFA狀態集合
|
|
ε-closure(T)
|
Us?Tε-closure(s)
|
|
move(T,a)
|
能夠從T中某個狀態S出發通過標號為a的轉換到達的NFA狀態的集合
|
Ø 構造D的狀態集合DStates和D的轉換函數Dtran
|
一開始,ε-closure(s)是DStates中的唯一狀態，且沒有被標記;
while (DStates中存在未被標識的狀態T) {
標識T;
for(每個輸入符號a) {
U = ε-closure(move(T,a));
if(U不再DStats中) 將U加入DStates，且沒有標識;
Dtran[T,a] = U;
}
}
|
Ø 計算ε-closure(T)的算法
|
將T的所有狀態壓入堆棧中;
將ε-closure(T)的內容初始化為T;
while (堆棧非空) {
將棧頂元素t彈出;
for(每個滿足如下條件的u：從t出發有一個標號為ε的轉換到達狀態u)
if(u不再ε-closure(T)中){
將u加入到ε-closure(T)中;
將u壓入棧中;
}
}
|
Ø 附模擬一個NFA
|
S = ε-closure(s0);
c = nextChar();
while(c != eof) {
S = ε-closure(move(S,c));
c = nextChar();
}
if(S ∩ F != ø) return true;
else return false;
|
</script>