NFA構(gòu)造DFA的子集算法
n 輸入：一個NFA N
n 輸出：一個DFA D
n 方法：為D構(gòu)造一個轉(zhuǎn)換表Dtran。D的每一個狀態(tài)是一組NFA狀態(tài)的集合。以下是一些構(gòu)造需要用到的函數(shù)。
|
操作
|
描述
|
|
ε-closure(s)
|
能夠從NFA的狀態(tài)s開始只通過ε轉(zhuǎn)換到達(dá)的NFA狀態(tài)集合
|
|
ε-closure(T)
|
Us?Tε-closure(s)
|
|
move(T,a)
|
能夠從T中某個狀態(tài)S出發(fā)通過標(biāo)號為a的轉(zhuǎn)換到達(dá)的NFA狀態(tài)的集合
|
Ø 構(gòu)造D的狀態(tài)集合DStates和D的轉(zhuǎn)換函數(shù)Dtran
|
一開始,ε-closure(s)是DStates中的唯一狀態(tài)，且沒有被標(biāo)記;
while (DStates中存在未被標(biāo)識的狀態(tài)T) {
標(biāo)識T;
for(每個輸入符號a) {
U = ε-closure(move(T,a));
if(U不再DStats中) 將U加入DStates，且沒有標(biāo)識;
Dtran[T,a] = U;
}
}
|
Ø 計(jì)算ε-closure(T)的算法
|
將T的所有狀態(tài)壓入堆棧中;
將ε-closure(T)的內(nèi)容初始化為T;
while (堆棧非空) {
將棧頂元素t彈出;
for(每個滿足如下條件的u：從t出發(fā)有一個標(biāo)號為ε的轉(zhuǎn)換到達(dá)狀態(tài)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>