dfa算法(dfa算法)

dfa和nfa的基本概念及其区别?

基本概念：

1. 确定有限自动机(Deterministic Finite Automaton) 简称DFA。dfa是匹配速度，是确定的。

2. 非确定有限自动机(Nondeterministic Finite Automaton) 简称NFA,nfa是匹配结果，是不确定的。

1. DFA比较快，但不提供Backtrack(回溯)功能，NFA比较慢，但提供了Backtrack功能。

2. NFA是基于表达式的(Regex-Directed)，而DFA是基于文本的(Text-Directed)。

3. DFA引擎在任意时刻必定处于某个确定的状态，而NFA引擎可能处于一组状态之中的任何一个，所以，NFA引擎必须记录所有的可能路径(trace multiple possible routes through the NFA)，NFA之所以能够提供Backtrack的功能，原因就在这里。dfa或nfa是对计算机程序的行为的抽象模型。你编写的程序其实就对应了一个自动机。简单举例来说，如果a,b可以取值0或1; 程序： if(a==1) b=1;这个程序对应了一个自动机。

对应的自动机就有状态 (0,0), (0,1), (1,1), (1, 0)

比如你自动机的初始状态是 (1,0)即a=1,b=0时，运行程序的下一个状态就是(1,1)。

画图出来就是 这4个状态作为顶点，并且有下面几条边

(0,0) --> (0,0)(自环),(1,0)-->(1,1),(1,1)-->(1,1)(自环), (0,1)-->(0,1)自环

存在的意义就是一种理论模型，也可以认为是一种编程思想。词法分析系也离不开 if else， 这一系列的if else和条件也就组成自动机。。。

最经典体现自动机思想的算法就是kmp算法，你肯定学过，字符串子串匹配的算法。 回忆这个算法的过程：算法第一步构造的next表(数据结构教材的说法)其实就是根据子串的内容构造了一个自动机！ 算法第二步将原串作为自动机输入，自动机的输出就是匹配到的子串位置或者无匹配。

dfa和nfa的基本概念及其区别?

基本概念：

1. 确定有限自动机(Deterministic Finite Automaton) 简称DFA。dfa是匹配速度，是确定的。

2. 非确定有限自动机(Nondeterministic Finite Automaton) 简称NFA,nfa是匹配结果，是不确定的。

1. DFA比较快，但不提供Backtrack(回溯)功能，NFA比较慢，但提供了Backtrack功能。

2. NFA是基于表达式的(Regex-Directed)，而DFA是基于文本的(Text-Directed)。

3. DFA引擎在任意时刻必定处于某个确定的状态，而NFA引擎可能处于一组状态之中的任何一个，所以，NFA引擎必须记录所有的可能路径(trace multiple possible routes through the NFA)，NFA之所以能够提供Backtrack的功能，原因就在这里。dfa或nfa是对计算机程序的行为的抽象模型。你编写的程序其实就对应了一个自动机。简单举例来说，如果a,b可以取值0或1; 程序： if(a==1) b=1;这个程序对应了一个自动机。

对应的自动机就有状态 (0,0), (0,1), (1,1), (1, 0)

比如你自动机的初始状态是 (1,0)即a=1,b=0时，运行程序的下一个状态就是(1,1)。

画图出来就是 这4个状态作为顶点，并且有下面几条边

(0,0) --> (0,0)(自环),(1,0)-->(1,1),(1,1)-->(1,1)(自环), (0,1)-->(0,1)自环

存在的意义就是一种理论模型，也可以认为是一种编程思想。词法分析系也离不开 if else， 这一系列的if else和条件也就组成自动机。。。

最经典体现自动机思想的算法就是kmp算法，你肯定学过，字符串子串匹配的算法。 回忆这个算法的过程：算法第一步构造的next表(数据结构教材的说法)其实就是根据子串的内容构造了一个自动机！ 算法第二步将原串作为自动机输入，自动机的输出就是匹配到的子串位置或者无匹配。