有人可以告诉我为什么将 NFA 转换为 DFA 有用的一些原因吗? 到目前为止我发现了以下原因(我不确定):
有人知道这种转换有用的另一个原因吗?
DFA 比 NFA 更快
是和不是。
一方面,给定的 DFA 当然比给定的 NFA 运行“更快”,因为运行 NFA 的算法需要以某种方式解决不确定性(例如,通过在运行时构建幂集)。
另一方面,否:相当于 NFA 的 DFA 也可能比 NFA 大很多,特别是当 NFA 使用幂集构造导出时。这样两者的运行时间将几乎相同。
但我认为这与这里的要点无关。我们正在谈论用于解决“理论”问题的计算抽象。我们从未在“真正的”计算机上实现 DFA,因此实际上不需要担心速度。
DFA 更容易实施这有点令人困惑。您的意思是说,提出执行 X 的 DFA 比执行 X 的 NFA 更容易?我非常不同意这一点,有时 NFA 是比 DFA 更好的解决问题的工具,有时 DFA 就足够了。
如果您的意思是更容易实现运行这些自动机的算法,那么您是对的,对于 DFA,您只需遵循转换函数即可。
回到你的主要问题。为什么要转换?
简而言之:如果你想运行 NFA,你必须消除非确定性,否则确定性算法无法执行它。问题是谁做的。可以运行 NFA 的算法可以为您做到这一点,如果您手头没有该工具,则需要事先对其进行转换。