dfa和nfa的区别
发布网友
发布时间:2023-05-04 11:39
我来回答
共1个回答
热心网友
时间:2023-10-28 20:27
基本概念:
确定有限自动机(Deterministic Finite Automaton) 简称DFA。dfa是匹配速度,是确定的。
非确定有限自动机(Nondeterministic Finite Automaton) 简称NFA,nfa是匹配结果,是不确定的。
区别:
DFA比较快,但不提供Backtrack(回溯)功能,NFA比较慢,但提供了Backtrack功能。
NFA是基于表达式的(Regex-Directed),而DFA是基于文本的(Text-Directed)。
DFA引擎在任意时刻必定处于某个确定的状态,而NFA引擎可能处于一组状态之中的任何一个,所以,NFA引擎必须记录所有的可能路径(trace multiple possible routes through the NFA),NFA之所以能够提供Backtrack的功能,原因就在这里。
扩展资料
一个程序要转换成词法分析器,词法分析器的任务就是将字符流转换成词法记号流,转换的核心在于有穷自动机的表示方法,有穷自动机与状态转换图有点相似,但它不是图,而是一个识别器,它对每个输入的'字符做识别和判断,以确定其能到达的最终状态或状态集和路径,有穷自动机分为两类,即不确定的有穷自动机NFA和确定的有穷自动机DFA。