Posted on 2007-09-06 22:09
ZelluX 阅读(393)
评论(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): 从同一状态出发的边可能标记有相同的符号
由于从同一状态出发选择的路径可能有多条，非确定性自动机总是需要进行“猜测”，而且总要做出正确的猜测。