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