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

Question

常に有限時間がかかる 2 つの (決定論的な) 有限状態マシンが等価であることを示す一般的な証明は存在しますか?つまり、2 つの FSM がある場合、同じ入力が与えられると、実際に FSM を実行する必要なく (終了しない可能性があります)、常に同じ出力が生成されることを証明できますか?そのような証明が存在する場合、時間計算量はどれくらいになるでしょうか?

Answer 1

私には分かりませんが、証拠はあります。このテーマに関するシプサーの教科書を探してください。私はそこからこのことを知りました。

記憶を漁ってみると、基本的に、特定の DFA には固有の最小 DFA があり、常に終了する最小化アルゴリズムが存在します。A と B の両方を最小化し、同じ最小 DFA を持つかどうかを確認します。最小化の複雑さはわかりませんが、それほど悪くはありません（多項式だと思います）。グラフの同型性の計算はかなり難しいですが、特別な開始ノードがあるため、多少は簡単になる可能性があります。正直に言うと、グラフの同型性さえ必要ないかもしれません。

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

Answer 2

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

@Agorは正しくSipserは、物事のこれらの種類のために良いの参照であることを述べています。私の答えの重要なポイントは、あなたも小さな指数で、多項式時間でこれを行うことができるということです。