与彼此相比，DFA 和 NFA 的相对优缺点是什么？
我知道 DFA 比 NFA 更容易实现，并且 NFA 到达接受状态的速度比 DFA 慢，但是还有其他明确的、众所周知的优点/缺点吗？
问问题
16109 次
3 回答
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 更慢但更简单（在相同的条件下）。
于 2011-05-12T21:12:42.403 回答
1
NFA 优于 DFA 的优势在于始终“选择正确的路径”的属性。由于您不能在算法中说“选择正确的路径”，通常从 NFA 到 DFA 的转换是有效的，创建象征多个 NFA 状态的 DFA 状态。因此，当您的 NFA 处于状态 A 并且可以选择进入 A、B 或 C 时，您的 DFA 中的下一个状态将是 {A,B,C}。
这解释了优点和缺点：DFA 可以更容易地实现，因为它们的下一个状态由函数确定。NFA 允许用户更轻松地表达他们想要的内容，因为 NFA 可以在许多路径之间进行选择。
于 2011-06-12T10:54:55.593 回答
0
NFA 相对于 DFA 的一个明显优势是，您可以使用 NFA 轻松构建表示语言的 FA，该语言是两种（或多种）语言的联合、交集、并列等。也就是说，如果你有稍微简单的 FA 做部分工作，你可以使用 NFA 轻松组合它们。使用 DFA 时，您需要构建一个新的自动机来完成所有工作。
看，它更容易实现。但正如你提到的，有时间问题。
于 2011-07-22T10:19:25.373 回答