与彼此相比,DFA 和 NFA 的相对优缺点是什么?
我知道 DFA 比 NFA 更容易实现,并且 NFA 到达接受状态的速度比 DFA 慢,但是还有其他明确的、众所周知的优点/缺点吗?
与彼此相比,DFA 和 NFA 的相对优缺点是什么?
我知道 DFA 比 NFA 更容易实现,并且 NFA 到达接受状态的速度比 DFA 慢,但是还有其他明确的、众所周知的优点/缺点吗?
NFA 和 DFA 接受相同的语言集 - 常规语言。
NFA 的直接实现(它不是 DFA,因为 DFA 是 NFA 的子集)通常涉及允许回溯,而 DFA 的直接实现只需要与输入长度一样多的步骤,因此从这个意义上说,DFA “到达在答案中“比等效的 NFA(不是 DFA)更快。
当试图找到与给定语言或 RE 对应的 FA 时(例如,通过算法),通常更容易首先到达 NFA(因为规则不那么严格)。在试图证明 FA 的存在时尤其如此,因为 NFA 的存在与 DFA 的存在一样好。如果需要 DFA,则存在用于 (a) 将 NFA 转换为等效 DFA 和 (b) 最小化 DFA 的算法。
概括地说,DFA 更快但更复杂(在状态和转换的数量方面),而 NFA 更慢但更简单(在相同的条件下)。
NFA 优于 DFA 的优势在于始终“选择正确的路径”的属性。由于您不能在算法中说“选择正确的路径”,通常从 NFA 到 DFA 的转换是有效的,创建象征多个 NFA 状态的 DFA 状态。因此,当您的 NFA 处于状态 A 并且可以选择进入 A、B 或 C 时,您的 DFA 中的下一个状态将是 {A,B,C}。
这解释了优点和缺点:DFA 可以更容易地实现,因为它们的下一个状态由函数确定。NFA 允许用户更轻松地表达他们想要的内容,因为 NFA 可以在许多路径之间进行选择。
NFA 相对于 DFA 的一个明显优势是,您可以使用 NFA 轻松构建表示语言的 FA,该语言是两种(或多种)语言的联合、交集、并列等。也就是说,如果你有稍微简单的 FA 做部分工作,你可以使用 NFA 轻松组合它们。使用 DFA 时,您需要构建一个新的自动机来完成所有工作。
看,它更容易实现。但正如你提到的,有时间问题。