NFA与DFA的优点/缺点相反

Question

DFA和NFA的相对亲和亲分别是什么？

我知道，DFA的相比，是容易NFA的和NFA的是慢比DFA的的接受状态到达，但还有没有其他明确的，众所周知的优点/缺点实现？

Answer 1

NFA的超过DFA的优点是财产，始终“选择正确的道路”。由于您无法在算法中选择“选择正确的路径”，因此通常会将NFA转换为DFA，从而创建符号化多个NFA状态的DFA状态。因此，当您的NFA处于A状态并且可以选择转到A，B或C时，您的DFA中的下一个状态将为{A，B，C}。

这解释的优点和缺点： DFA的可以，因为他们的下一个状态是由功能决定实施更加容易。 NFA允许用户更容易地表达他们想要的内容，因为NFA可以在多个路径之间进行选择。

Answer 2

的NFA和DFA的接受同一组的语言 - 正规语言。

NFA（不是DFA，因为DFA是NFA的一个子集）的直接实现通常涉及允许回溯，而直接实现DFA只需要与输入长度一样多的步骤，所以在这个意义上，DFA“比”等效的NFA（不是DFA）更快地得出答案。

当试图找到对应于给定语言或RE（例如，通过一种算法）一个FA，它通常更容易在NFA首先到达（因为规则是不太严格的）。当试图证明FA的存在时尤其如此，因为NFA的存在与DFA的存在一样好。如果需要DFA，则存在以下算法（a）将NFA转换为等效的DFA和（b）将DFA最小化。

制作总概括的DFA更快但更复杂的（在状态和转换的数量而言），而是NFA的速度较慢，但​​更简单的（在相同的条件）。

Answer 3

NFA超过DFA的一个明显优势是，您可以使用NFA轻松构建FA代表两种（或更多）语言的联合，交集，静止等语言。也就是说，如果你有一些简单的FA做部分工作，你可以使用NFA来轻松地组合他们。在使用DFA时，您需要建立一个自动完成所有工作的新自动机。

看，实施起来比较容易。 但你提到的时间问题。