有限時間における2つのFSMの等価性の一般的証明？

Question

常に有限時間を要する2つの（確定的な）有限状態マシンの等価性についての一般的な証明はありますか？つまり、2つのFSMがある場合、同じ入力を与えられても、実際にFSMを実行する必要はなく（常に終了しない可能性があります）、同じ出力を生成することが証明できますか？そのような証明が存在する場合、時間の複雑さは何ですか？

Answer 1

私にはわかりませんが、証拠があります。件名のSipserの教科書を探してください。それは私が知っているところです。

私のメモリをスクロールする：基本的に、特定のDFAに固有の最小限のDFAがあり、常に終了する最小化アルゴリズムがあります。 AとBの両方を最小化し、同じ最小DFAを持っているかどうかを確認します。私は最小化の複雑さを知らないが、それほど悪くない（私はその多項式と考える）。グラフ同型写像は計算が非常に難しいですが、特殊な開始ノードがあるので、やや簡単になるかもしれません。正直言って、同型写像は必要ないかもしれません。

ただし、実際にDFAを実行する必要はなく、構造を分析するだけです。

Answer 2

O（n）の状態の2つのFSMがあるとします。次に、受け入れ言語の対称差のみを認識するサイズO（n ）のFSMを作成できます。 （各FSMからの状態のペアに対応する状態を持つFSMを作成し、各ステップでペアの各部分を同時に更新する）新しいFSMの状態は、受け入れ状態）。このFSMを最小限にし、すべてを拒否する簡単な1状態FSMと同じかどうかを確認します。 メートル状態にFSMを最小化することは、（メートルログメートル）時間Oをとり、その全体的なあなたは、時間O（nは ログN）ですべてを行うことができます。

@Agorは、Sipserがこれらの種類のものの良いリファレンスであることを正しく示しています。私の答えのポイントは、たとえ小さな指数であっても、多項式時間でこれを行うことができるということです。