algorithm - DFA 構造の補数を見つける

Question

だから私はdfaを補数に変換する方法に取り組んでいます。補数は、dfa が受け入れるすべての文字列を拒否し、dfa が拒否するすべての文字列を受け入れます。これを行うには、次のアルゴリズムに従うことになっています。「最初に明示的なデッド ステートを追加し、それへのすべての遷移を明示的に行います。次に、すべての最終状態を非最終状態に変更し、すべての非最終状態を最終状態に変更します。」

私はこれを試してみましたが、成功しませんでした。正しく理解できていないと思います。

最初に、すべての最終状態を非最終状態に変更し、非最終状態を最終状態に変更しました。

次に、各状態について、アルファベットによる遷移がない場合は、それらのアルファベットを使用して、その状態から明示的なデッド状態への遷移を追加しました。

これは正しいです？

Answer 1

いいえ、特定のシンボルによる特定の状態からの遷移がないように、最初にすべての状態とシンボルの新しく作成されたデッド ステートに遷移する必要があります。その後、すべての最終状態を非最終状態にし、その逆も同様です。この順序で行うと、dead 状態が final になり、まさにそれが起こるはずです (dead 状態に達すると、指定された文字列は元のオートマトンによって受け入れられません。したがって、その補数によって受け入れられる必要があります)。