NFA相对于DFA的优缺点及反之

Question

3

与NFA相比，DFA在实现上更容易；而NFA到达接受状态的速度较慢。除此之外，是否存在其他明确的、众所周知的优势/劣势呢？

- user559142

3个回答

1

NFA比DFA的优势在于始终能够“选择正确的路径”。由于你不能在算法中说“选择正确的路径”，通常从NFA转换为DFA，创建代表多个NFA状态的DFA状态。因此，当你的NFA处于状态A并且可以选择前往A、B或C时，则你的DFA中的下一个状态将是{A，B，C}。

这解释了优点和缺点： DFA更容易实现，因为它们的下一个状态是由函数确定的。 NFA允许用户更轻松地表达他们想要的，因为NFA可以在许多路径之间进行选择。

- grackkle

0

NFA相对于DFA的一个明显优势是，你可以使用NFA轻松地构建表示两个（或多个）语言的并集、交集、连接等的FA。也就是说，如果你有一些简单的FA分别完成部分工作，你可以使用NFA轻松地将它们组合起来。而使用DFA，则需要构建一个新的自动机来完成所有工作。

可以看出，这样实现起来更容易。但正如你所提到的，时间问题也是需要考虑的。

- bliss

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Patrick · Accepted Answer

NFAs和DFAs接受相同的语言集合——正则语言。

直接实现NFA（它不是DFA，因为DFA是NFA的子集）通常涉及允许回溯，而直接实现DFA仅需要与输入长度相同数量的步骤，因此在这个意义上，DFAs比等效的NFAs“更快地到达答案”。

当试图找到与给定语言或RE相对应的FA（例如通过算法）时，通常更容易首先到达NFA（因为规则较不严格）。尤其是在试图证明FA存在性时，这一点尤为正确，因为NFA存在就好像DFA存在。如果需要DFA，那么有算法可以（a）将NFA转换为等价的DFA，以及（b）最小化DFA。

粗略概括地说，DFAs更快但更复杂（在状态和转换次数方面），而NFAs更慢但更简单（在相同的术语中）。