在线性时间和空间复杂度中遍历自动机的状态

Question

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

还有，在线性时间和空间中是否存在将NFA转换为DFA的算法?

Answer 1

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

但是，您可以使用矩阵来实现。