algorithm - 以线性时间和空间复杂度遍历自动机的状态

Question

如何以线性时间和空间复杂度遍历自动机的状态？如何将状态/转换表示为数据结构？

还有，有没有在线性时间和空间上将NFA转换为DFA的算法？

Answer 1

实现取决于确切的应用程序。在一般情况下，您始终可以将其实现为具有多个传出链接的节点。在这种情况下，转换是 O(1)。

但是，您可以使用矩阵来实现。尤其是当转换密集时。