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。