dfa和nfa的区别

基本概念：

确定有限自动机(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。

既然你都知道它们是怎么回事儿了，怎么会不明白它们和词法分析程序的关系呢？

简单点儿说，词法分析就是进行正则表达式匹配。词法分析程序就是根据要匹配的正则表达式生成它的NFA或者DFA，再将待匹配的字符串放到这些NFA或者DFA中进行处理，从而分析出输入字符串是否匹配给定的正则表达式。

f函数定义有错误，需要改成

int f(int x,char e)

{ int df[4][2]={{2,3},{4,3},{2,4},{4,4}}

int i

if(e=='a')

i=df[x-1][0]

if(e=='b')

i=df[x-1][1]

return(i)

}

---