6

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

4

1 回答 1

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

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

于 2015-08-31T09:39:57.140 回答