NFA与DFA工作的区别,dfa与nfa的基本概念及其区别

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。

简述什么是DFA和NFA的区别求大神帮助

一个是匹配速度。DFA快一些 一个是匹配结果。DFA 是确定的。。而NFA 是不确定的

算法设计-帮帮忙

这个估计要用文件输入

否则太累了

--我们必须尽量优化程序才能达到题目的要求。显然n实在是太大了，所以我们不但不可能忍受O(n2)的复杂度，甚至连n前面的系数过大都会造成超时。为了尽量减小时间复杂度，我们只能依靠自动机的理论。

自动机理论

一个DFA（确定性有限自动机）是一个五元组∑, U, s, T, φ，其中∑是字符集U 是一个有限的状态集合, s 是 U 的一个元素表示初始状态, T 是 U的一个子集，表示终止状态and φ : U × ∑ → U 是转移函数。

开始时自动机在初始状态s，每步它读入一个字符c，然后根据state=φ(state,c)进行状态的转移。如果当字符串结束时它达到了终止状态，那么就说它接受了字符串。

NFA（非确定性自动机）与DFA的主要区别就是，NFA从一个状态按照一个字符转移到的状态可能有多个。因此NFA需要使用一个状态集合来表示当前可能处在的状态。

把自动机用图来表示的话，一般用结点表示状态，而结点之间有标有某个字符的有向边，表示可以从边的起点通过这个字符转移到边的终点。

此外NFA还可以包含标有ε的边，这种边表示不需要任何字符就可以直接进行状态的转移。

容易想到，如果我们建立了一个只接受符合正则表达式的自动机，就可以通过它来较快的判断哪些位置是可匹配的。

具体应用

比较常见的字符串匹配自动机大多都是DFA。但是由于有+，*，把正则表达式直接转变成DFA是非常困难的。因此我们只能先把它转化成NFA。

先看一下一般的转换规则：

如果正则表达式是一个字符，那么对应的NFA是：

p0-a-p1

如果正则表达式是A+B的形式，那么只要把它们的起始状态和终止状态合并就可以：

p0-a-p1

p0-b-p1

如果正则表达式是AB的形式，那么只要把A和B对应的自动机首尾相接：

p0-a-p1-b-p2

如果正则表达式是A*的形式，那么就需要按下面的图来进行处理：

p0-a-p0

p0-p1

通过上面的步骤可以得出：NFA的状态数不会超过正则表达式长度。

NFA中的状态转移

在NFA中进行状态转移比DFA要困难一些。我们可以定义两个函数，一个叫做epsilon-closure，用来计算一组NFA状态通过epsilon边能够到达的NFA状态集合。另外一个move用来在NFA上进行状态的转移。

设当前的状态集合是now，那么状态转移的过程就是：

new = {}

for every state s in now do

new = new ∪ {t | (s,t) = c}

new = epsilon_closure(new)

其中的(s,t)=c表示从s状态经过一个字符c可以转化到t状态。因为这个语句需要的集合总数也不会太多，所以可以通过预先计算出它们来加快速度。预处理后这个过程的复杂度是O(m2)，而系数是比较小的。

但是由于在NFA中，我们必须把状态的集合作为一个真正的状态，每次状态转移都是对这个集合的处理。这样转移一次的复杂度是O(m2)，这是不可忍受的（最大的数据需要大约2分钟才能出解）。

既然NFA速度过慢，我们自然想要把它转化为DFA。因为DFA中的状态转移是O(1)的。可是并没有一个多项式复杂度的方法可以把NFA转换成DFA。一般介绍的NFA转换到DFA的方法都是通过类似BFS的方法来把NFA中所有可能出现的状态集合对应成DFA的一个状态。

这种转换在本题中显然是不可行的，因为NFA的结点数最多是500，而转化成的DFA则可能有多达2500个状态，即使实际有许多状态不能达到，也是无论如何不可以忍受的。

看来把NFA转换成DFA是行不通的。但是我们还是从NFA转DFA的过程中受到了一些启发：NFA之所以速度慢，是因为我们在进行状态转移的时候可能进行许多重复操作：比如从{1,2}沿一个字符1转移后是{2,3}，以后我们还可能遇到相同的情况，而这时我们还会用O(m2)的时间去进行状态转移。这是一种很严重的浪费。因此我们每进行一次状态转移，就把这个状态转移的情况放到hash表中，以后使用的时候就可以查找了。这相当于只把我们需要的一部分子集转移成DFA，虽然一般情况下并不能降低时间复杂度，但是在实际应用中确实很有效。（特别是对于没有*和括号的自动机，这样做可以保证线形的时间复杂度）

算法回顾和细节

我们重新来看一下算法的框架：

根据正则表达式建立NFA

now = start

while not eof do begin

read(c);

if 曾经进行过now,c的转移 then 利用以前的结果

else 进行状态转移并记录结果

if 终止状态 in now then 输出当前位置

end

建立NFA有各种方法，由于NFA并不会很大，所以我们可以使用递归的方法来实现。为了尽量减小系数，我们使用位压缩的方式来实现集合，并采用较为简化的hash函数（比如把一个集合位压缩后的一系列整数加起来取对220的余数），并在输入和输出的时候通过缓冲区来加快速度。这样就基本可以达到题目的时间要求。

但是注意到字符串可能有10M，而产生的NFA的状态集合最多也可能有10M个，而每个集合都需要100到200字节的存储空间，大大超出了允许的空间范围。因此我们需要对hash表的规模加以严格限制。如果规模过大就不得不放弃存储状态的想法，牺牲一定的时间来换取空间。

dfa与nfa有何区别

一个是匹配速度。DFA快一些

一个是匹配结果。DFA 是确定的。。而NFA 是不确定的