compiler-construction - nfa 与 dfa 的时间复杂度权衡

Question

我正在寻找关于哪个更好地使用以及在编译器中的 nfa 或 dfa 的情况下的讨论。模拟 nfa 与 dfa 的时间复杂度权衡是什么，在编译器的什么情况下哪个更适合？

Answer 1

从 NFA 构建 DFA 的时间为 O(2^m)，其中 m 是节点数。

DFA 的运行时间为 O(n)，其中 n 是输入字符串的长度。这是因为对于给定的字符串，只有 1 条路径通过 DFA。

NFA 的构建时间应该是 O(m)，其中 m 是节点数

NFA 的运行时间是 O(m²n)，因为它是不确定的，计算机必须检查字符串中当前字符的每条可能路径。 (假设没有前瞻，它不知道下一个字符是什么，所以它会陷入死胡同)

这些数字可能会给你一个简短的想法