finite-automata - NFA 相对于 DFA 的优点/缺点，反之亦然

Question

相互比较时，DFA 和 NFA 的优缺点是什么？

我知道 DFA 比 NFA 更容易实现，而且 NFA 比 DFA 更慢地到达接受状态，但是还有其他明显的、众所周知的优势/劣势吗？

Answer 1

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

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

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

总的来说，DFA 速度更快但更复杂(在状态和转换的数量方面)，而 NFA 速度更慢但更简单(在相同条件下)。