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

Question

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

Answer 1

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

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

しかし、DFA を実際に実行する必要はありません。構造を分析するだけです。

Answer 2

O( n ) 状態の 2 つの FSM があるとします。次に、受け入れる言語の対称的な違いのみを認識するサイズ O( n ^{2 ) の FSM を作成できます。}(各 FSM から 1 つずつ、状態のペアに対応する状態を持つ FSM を作成します。次に、各ステップで、ペアの各部分を同時に更新します。新しい FSM の状態は、ペアの 1 つだけがあった場合、受け入れ状態です。次に、この FSM を最小化し、すべてを拒否する自明な 1 状態 FSM と同じかどうかを確認します。m 個の状態を持つ FSM を最小化するには O( m log m ) の時間がかかるため、全体として O( n ² log n )の時間ですべてを実行できます。

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