compiler-construction - nfa与dfa的时间复杂度折衷

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

最佳答案

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

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

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

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

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

关于compiler-construction - nfa与dfa的时间复杂度折衷，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/4580654/