nfa 与 dfa 的时间复杂度权衡

Question

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

Answer 1

\n
• 从 NFA 构造 DFA 的时间为 O(2^m)，其中 m 是节点数。
\n
• DFA 的运行时间为 O(n)，其中 n 是输入字符串的长度。这是因为对于给定字符串，只有 1 个通过 DFA 的路径。
\n
• NFA 的构建时间应该是 O(m)，其中 m 是节点数
\n
• NFA 的运行时间为 O(m\xc2\xb2n)，因为它是不确定的，并且计算机必须检查字符串中当前字符的每个可能路径。（假设没有前瞻，它不知道下一个字符是什么，所以它会陷入死胡同）
\n

\n\n

这些数字可能会让你有一个简单的了解

\n