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