Ullman et al. による "Introduction to the Automata Theory, Languages and Computation"、第 2 版、151 ページで、DFA を正規表現に変換する際の時間計算量の分析を見ています。この方法は、推移閉包法と呼ばれることもあります。O((n^3)*(4^n)) 時間の複雑さで 4^n 式をどのように思いついたのかわかりません。
空間の複雑さに関しては 4^n の式が成り立つことは理解していますが、時間の複雑さに関しては、前の繰り返しの結果を使用して、各反復で状態の各ペアに対して 4 つの定数時間操作のみを実行しているようです。私は正確に何が欠けていますか？
あなたの疑問はn 3 Time Complexity に関するものだと思います。
R ij kが、オートマトンを状態 q iからq jに遷移させ、 q kよりも高い状態を通過しないすべての文字列のセットを表すと仮定します。
次に、 R ij kの反復式を以下に示します。
R ij k = R ik k-1 (R kk k-1 ) * R kj k-1 + R ij k-1 .
この手法は、全ペア最短経路問題に似ています。唯一の違いは、距離を合計するのではなく、正規表現の結合と連結を行っていることです。全ペア最短経路問題の時間計算量はn 3です。DFAそのため、 to Regular ExpressionConversion についても同じ複雑さが予想されます。同じ方法を使用して、対応する正規表現に変換することもできNFAますε-NFA。
の主な問題transitive closure approachは、非常に大きな正規表現が作成されることです。この長い長さは、連結された用語の結合が繰り返されるためです。