Posted on 2007-09-06 22:09
ZelluX 閱讀(406)
評論(0) 編輯 收藏 所屬分類:
Courses
DFA(deterministic finite automaton): 從同一狀態(tài)出發(fā)的邊都標(biāo)記有不同的符號
可以把一個DFA用一個轉(zhuǎn)置矩陣(transition matrix)表示，矩陣的第i行記錄狀態(tài)i向其他狀態(tài)跳轉(zhuǎn)的情況，edges[i][j]表示狀態(tài)i時吃掉一個j符號后跳轉(zhuǎn)到edges[i][j]狀態(tài)。
DFA的一個好處就是可以識別最長的匹配，比如對于IF8這個字符串，可以被識別為一個變量而不是一個關(guān)鍵字加數(shù)字。
處理方法是保留最后一次自動機的終結(jié)狀態(tài)Last-Final及其相對應(yīng)的字符位置Input-Position-at-Last-Final。
每次進入一個終結(jié)狀態(tài)，就更新這兩個變量。
遇到死路(dead state, a nonfinal state with no output transitions)，通過這兩個變量回復(fù)到上一個終結(jié)狀態(tài)。
NFA(nondeterministic finite automaton): 從同一狀態(tài)出發(fā)的邊可能標(biāo)記有相同的符號
由于從同一狀態(tài)出發(fā)選擇的路徑可能有多條，非確定性自動機總是需要進行“猜測”，而且總要做出正確的猜測。