知止而后有定，定而后能靜，靜而后能安，安而后能慮，慮而后能得。物有本末，事有終始。知所先后，則近道矣。
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));
if(S ∩ F != ø) return true;
else return false;
</script>
Powered by: BlogJava Copyright © helloworld2008