3

与彼此相比,DFA 和 NFA 的相对优缺点是什么?

我知道 DFA 比 NFA 更容易实现,并且 NFA 到达接受状态的速度比 DFA 慢,但是还有其他明确的、众所周知的优点/缺点吗?

4

3 回答 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 回答