我正在查看将dfa转换为正则表达式的时间复杂度分析《自动机理论、语言和计算导论》，第二版，第151页，Ullman等人著。此方法有时称为传递闭包方法。我不明白他们是如何在O((n^3)*(4^n))时间复杂度中提出4^n表达式的。
我理解关于空间复杂度的4^n表达式成立，但是，关于时间复杂度，似乎我们在每次迭代中使用前一次迭代的结果，对每对状态只执行四个常数时间操作。我到底错过了什么?
这是没有使用正确数据结构的算法复杂性的粗略界限。我认为除了作者显然不关心优化之外，没有什么需要解释的，可能是因为他们的主要观点是正则表达式至少和dfa一样具有表现力，因为他们觉得优化这个指数时间算法是毫无意义的。
有三个嵌套循环，每个循环n次迭代;在外部循环的第k次迭代期间构造的正则表达式的大小归纳为O(4^k)，因为它们是由前一次迭代期间构造的最多四个正则表达式构造而成的。如果算法复制这些子表达式，并且我们在所有迭代中高估正则表达式的大小界限为O(4^n)，那么我们得到O(n^3 4^n)。
显然我们可以做得更好。在不消除复制的情况下，我们可以得到O(sum_{k=1}^n n^2 4^k) = O(n^2 (n + 4^n))通过适当地限定几何和。此外，正如您所指出的，我们根本不需要复制，除非在最后，如果我们同意templatetypedef的输出必须完全写出来，则给出O(n^3)的运行时间来准备正则表达式，O(4^n)来将其写出来。这个版本的空间复杂度等于时间复杂度
我想你的疑问是关于n3时间复杂度。
让我们假设Rijk表示将自动机从状态qi转换到qj而不经过任何高于qk的所有字符串的集合。
则Rijk的迭代公式如下:
R <子> ij <一口> k = R本土知识<子><一口> k - 1> kk <一口> k - 1> * R <子> kj <一口> k - 1> ij <一口> k - 1 。
该技术类似于全对最短路径问题。唯一的区别是我们对正则表达式进行并并和连接，而不是对距离求和。全对最短路径问题的时间复杂度为n3。所以我们可以预期DFA到Regular Expression的转换也有相同的复杂度。同样的方法也可以将NFA和ε-NFA转换为相应的正则表达式。
transitive closure approach的主要问题是它创建了非常大的正则表达式。如此大的长度是由于连接项的重复并集。