DFAの最小化 – 日本の辞書

DFA_minimization
オートマトン理論（理論計算機科学の一分野）では、DFA最小化は、特定の決定性有限オートマトン（DFA）を最小数の状態を持つ同等のDFAに変換するタスクです。ここで、2つのDFAは、同じ正規言語を認識する場合、同等と呼ばれます。このタスクを実行するいくつかの異なるアルゴリズムが知られており、オートマトン理論に関する標準的な教科書に記載されています。
DFAの例。状態の場合 c { c}
、すべての入力文字列に対して、状態と同じ動作を示します d { d}
、または状態 e { e}
。同様に、 a { a}と b
{ b}
区別できません。DFAには到達不能な状態はありません。
同等の最小DFA。区別できない状態が1つに統合されました。

コンテンツ
1 最小限のDFA
2 到達不能な状態
3 区別できない状態
3.1 ホップクロフトのアルゴリズム 3.2 ムーアのアルゴリズム 3.3 Brzozowskiのアルゴリズム
3.3.1 正当性の証明
3.3.2 複雑
4 NFAの最小化
5 も参照してください
6 ノート
7 参考文献
8 外部リンク

最小限のDFA
正規言語ごとに、それを受け入れる最小のオートマトン、つまり、状態の数が最小のDFAも存在し、このDFAは一意です（状態に異なる名前を付けることができることを除いて）。最小限のDFAにより、パターンマッチングなどのタスクの計算コストを最小限に抑えることができます。
受け入れる言語に影響を与えることなく、元のDFAから削除またはマージできる状態には2つのクラスが
到達不能状態とは、どの入力文字列についても、DFAの初期状態から到達できない状態です。これらの状態は削除できます。
デッド状態は、最終状態に到達できない状態です。オートマトンを完了する必要がない限り、これらの状態は削除できます。
区別できない状態とは、どの入力文字列でも互いに区別できない状態です。これらの状態はマージできます。
DFAの最小化は、通常3つのステップで実行されます。
デッド状態と到達不能状態を削除します（これにより、次のステップが加速されます）、
区別できない状態をマージし、
結果のDFAを完了する必要がある場合は、単一のデッド状態（「シンク」状態）を再作成します。

到達不能な状態
で信頼できる情報源に引用を追加して、このセクションの改善にご協力調達されていない資料は、異議を申し立てられ、削除される可能性が
状態 p { p}
$p""$
決定性有限オートマトンのM =（（ Q Σ δ q 0 F ）。
{ M =（Q、 Sigma、 delta、q_ {0}、F）}

文字列がない場合は到達不能です w { w}

の
Σ ∗ { Sigma ^ {*}}

存在するp = δ ∗（（ q 0 w ）。
{ p = delta ^ {*}（q_ {0}、w）}

。この定義では、 Q { Q}

状態のセットです、 Σ { Sigma}

入力記号のセットです。 δ { delta}

遷移関数（状態と入力シンボルを状態のセットにマッピングする）であり、
δ ∗ { delta ^ {*}}

文字列への拡張（別名拡張遷移関数）であり、 0
{ q_ {0}}

は初期状態であり、 F { F}

受け入れ（別名最終）状態のセットです。到達可能な状態は、次のアルゴリズムで取得できます。
到達可能状態にしましょう：= { q0 }; new_states ：= { q0 } ; do { temp ：= 空のセット; new_statesの各qに対して、Σの各cに対してdo temp ：= temp∪ { p = δ （q 、c ）} ; _ 終了; 終了; new_states ：= temp 到達可能状態; Reachable_states ：= reachable_states∪new_states ; _ } while （new_states ≠空のセット）;
unreachable_states ：= Q Reachable_states ;
new_statesセット（例）とそれらに対する操作（状態の追加や存在するかどうかのチェックなど）の効率的な実装を想定すると、このアルゴリズムは時間計算量で実装できます。 O （（ n+ m ）。 { O（n + m）}

、どこ n { n}

状態の数であり、 m { m}

入力オートマトンの遷移の数です。
到達不能な状態は、受け入れる言語に影響を与えることなく、DFAから削除できます。

区別できない状態
次のアルゴリズムは、区別できない状態をマージするためのさまざまなアプローチを示しています。

ホップクロフトのアルゴリズム
Hopcroft（1971）によるDFAの区別できない状態をマージするための1つのアルゴリズムは、パーティションの改良に基づいており、DFA状態をそれらの動作によってグループに分割します。これらのグループは、マイヒル-ネロード同値関係の同値類を表します。これにより、すべての入力シーケンスで同じ動作をする場合、同じパーティションの2つの状態ごとに同値になります。つまり、パーティションP内の同じ同値類に属する2つの状態p1とp2ごと、およびすべての入力単語wについて、 wによって決定される遷移は、常に状態p1とp2を等しい状態にする必要が両方が受け入れるか、両方が拒否すると述べます。wがp1を受け入れ状態にし、p 2を拒否状態にしたり、その逆を行ったりすることはできません。
次の擬似コードは、Xuによって与えられるアルゴリズムの形式を説明しています。代替フォームも提示されています。
P ：= { F 、 Q F }; W ：= { F 、 Q F }; （Wは空ではありません）Σの各cのWからセットAを選択して削除します。Xを、Cの遷移がPの各セットYのAの状態につながる状態のセットとします。∩Yは空ではなく、Y Xは空ではありません。PのYを2つのセットXに置き換えます。_ _ _ _ _ _ _ _ _ _ _ _ _ X∩Y | _ _ <= | Y X | X∩YをWに追加します。それ以外の場合はY XをWに追加します。終了; 終了;
アルゴリズムは、粗すぎるパーティションから始まります。マイヒル-ネロードの関係に従って同等である状態のすべてのペアは、パーティション内の同じセットに属しますが、同等でないペアも同じセットに属する可能性がそれは、パーティションを徐々により多くのより小さなセットに洗練し、各ステップで状態のセットを必然的に同等ではないサブセットのペアに分割します。最初のパーティションは、状態を2つの状態のサブセットに分離することであり、これらは明らかに互いに同じ動作をしません。つまり、受け入れ状態と拒否状態です。次に、アルゴリズムは現在のパーティションと入力シンボルcからセットAを繰り返し選択し、パーティションの各セットを2つの（おそらく空の）サブセットに分割します。入力シンボルcでAにつながる状態のサブセットとAにつながらない状態のサブセット。Aは、パーティションの他のセットとは異なる動作をすることがすでに知られているため、Aにつながるサブセットも、Aにつながらないサブセットとは異なる動作をします。このタイプの分割が見つからなくなると、アルゴリズムは終了します。
補題。固定文字cと、同値類BとCに分割される同値類Yが与えられた場合、パーティション全体を改良するために必要なのは、BまたはCのいずれか1つだけです。
例：同値類BとCに分割される同値類Yがあるとします。クラスD、E、Fもあるとします。DとEには、文字cでBに遷移する状態があり、Fには文字cでCに遷移する状態が見出語では、BまたはCのいずれかを区別子として選択できます。たとえば、Bです。次に、DとEの状態は、Bへの遷移によって分割されます。ただし、Bを指さないFは、単純に分割されません。アルゴリズムの現在の反復中。それは他の識別者によって洗練されます。
観察。D、E、Fなどの参照クラスを正しく分割するには、BまたはCのすべてが必要です。サブセットではできません。
最も外側のifステートメント（YがWにある場合）の目的は、識別子のセットであるWにパッチを適用することです。アルゴリズムの前のステートメントで、Yが分割されたばかりであることがわかります。YがWにある場合、将来の反復でクラスを分割する手段として廃止されたばかりです。したがって、上記の観察のために、Yを両方の分割に置き換える必要がただし、YがWにない場合は、上記の見出語のため、2つの分割のうちの1つだけをWに追加する必要が両方を追加する必要はありません。2つの分割のうち小さい方を選択すると、Wへの新しい追加がYの半分以下のサイズになることが保証されます。これがホップクロフトアルゴリズムの核心です。次の段落で説明するように、どのように速度を上げるかです。
このアルゴリズムの最悪の場合の実行時間はO（ns log n）です。ここで、nは状態の数、sはアルファベットのサイズです。この限界は、オートマトンのns遷移のそれぞれについて、遷移のターゲット状態を含むQから引き出されたセットのサイズが、互いに対して2倍以上減少するため、各遷移が2倍以上減少するという事実に基づいています。アルゴリズムの分割ステップのO（log n）に参加します。パーティションリファインメントデータ構造により、各分割ステップは、それに参加する遷移の数に比例して時間内に実行できます。これは、問題を解決するために知られている最も効率的なアルゴリズムであり、入力の特定の分布では、その平均的なケースの複雑さはさらに優れています、O（n log log n）。
Hopcroftのアルゴリズムを使用して入力DFAの状態を同値類にグループ化すると、同値類ごとに1つの状態を形成することで最小DFAを構築できます。SがPの状態のセットであり、sがSの状態であり、cが入力文字である場合、入力cでのSの状態からの最小DFAの遷移は、入力オートマトンは、入力cの状態sから移行します。最小DFAの初期状態は、入力DFAの初期状態を含む状態であり、最小DFAの受け入れ状態は、メンバーが入力DFAの状態を受け入れている状態です。

ムーアのアルゴリズム
DFA最小化のためのムーアのアルゴリズムは、エドワードF.ムーア（1956）によるものです。Hopcroftのアルゴリズムと同様に、受け入れ状態と拒否状態の分離から始まるパーティションを維持し、それ以上の調整ができなくなるまでパーティションを繰り返し調整します。各ステップで、現在のパーティションをs + 1パーティションの最も粗い一般的な改良に置き換えます。そのうちの1つは現在のパーティションで、もう1つは各入力シンボルの遷移関数の下での現在のパーティションのプレイメージです。この置換によって現在のパーティションが変更されない場合、アルゴリズムは終了します。その最悪の場合の時間計算量はO（n 2 s）です。アルゴリズムの各ステップは、基数ソートのバリアントを使用して時間O（ns）で実行され、新しいパーティションの同じセット内の状態が次のようになります。順序付けは連続しており、各ステップから最大nステップありますが、最後のステップではパーティション内のセット数が増加します。最悪の場合の動作を引き起こすDFA最小化問題のインスタンスは、ホップクロフトのアルゴリズムの場合と同じです。アルゴリズムが実行するステップ数はnよりもはるかに少ない可能性があるため、平均して（定数sの場合）、そのパフォーマンスは、選択されたオートマトンのランダム分布に応じて、O（n log n）またはO（n log log n）になります。アルゴリズムの平均的な動作をモデル化します。

Brzozowskiのアルゴリズム
非決定性有限オートマトン（NFA）の遷移を反転する M { M}

初期状態と最終状態を切り替えると、NFAが生成されますM R
{ M ^ {R}}

元の言語の逆転のために。標準のパワーセット構造を使用してこのNFAをDFAに変換すると（変換されたDFAの到達可能な状態のみを保持）、DFAになりますM D R
{ M_ {D} ^ {R}}

同じ逆言語の場合。Brzozowski（1963）が観察したように、この逆転と決定性を2回繰り返し、再び到達可能な状態のみを維持することで、元の言語の最小のDFAが生成されます。
アルゴリズムの背後にある直感は次のとおりです。逆オートマトンを決定すると、元のオートマトンでは区別できない状態がマージされますが、マージされるべきではない（つまり、最小DFAではマージされない）状態もマージされる可能性がこのような場合、オートマトンを2回反転させた後は、決定論的ではない可能性がそのため、最小限のDFAを取得して、再度決定する必要が

正当性の証明
決定した後
M R { M ^ {R}}

取得する MD R { M_ {D} ^ {R}}

、これを逆にします MD R { M_ {D} ^ {R}}

取得する（（ MD R
）。 R =M ′
{（M_ {D} ^ {R}）^ {R} = M ‘}

。今M ′
{ M ‘}

と同じ言語を持っています M { M}

、ただし、重要な違いが1つ
M ′ { M ‘}

そこから同じ言葉を受け入れることができます。これはから続くM D R
{ M_ {D} ^ {R}}

決定論的であること、すなわち。に2つの州はありませんM D R
{ M_ {D} ^ {R}}

、同じ言葉で初期状態から到達できます。の決定M ′
{ M ‘}

次に、powerstates（の状態のセット）を作成します
M ′ { M ‘}

）、2つのパワーステートごとに R S { { mathcal {R}}、{ mathcal {S}}}

少なくとも1つの状態で-当然-異なる q { q}

の
M ′ { M ‘}

。推定q ∈ R
{ q in { mathcal {R}}}

とq ∉ P
{ q not in { mathcal {P}}}

; それから q { q}

の言語に少なくとも1つの単語を提供します R { { mathcal {R}}}
P
{ { mathcal {P}}}

、この単語はに固有であるため q { q}

（他の州はそれを受け入れません）。これは、パワーステートの各ペアに当てはまることがわかります。したがって、各パワーステートは、他のすべてのパワーステートと区別できます。したがって、M ′
{ M ‘}

、区別できない状態や到達できない状態のないDFAがしたがって、最小限のDFAM ¯
{ { overline {M}}}

オリジナルの M { M}

。
もしも M { M}

はすでに決定論的であるため、それをトリミングし、反転し、確定してから、再度反転するだけで十分です。これは、M D R
{ M_ {D} ^ {R}}

上記のプロセスでは（すでにトリミングされていると仮定して）、入力FAはすでに決定論的であるためです（ただし、実際には反転ではないことに注意してください）。逆転して決定するM D R
{ M_ {D} ^ {R}}

取得するM ¯
{ { overline {M}}}

、これは言語の逆転のための最小のDFAです M { M}

（これまでに1回だけ反転を行ったため）。今やるべきことは、逆転することだけですM ¯
{ { overline {M}}}

元の言語の最小限のDFAを取得します。

複雑
Brzozowskiのアルゴリズムの最悪の場合の複雑さは、入力オートマトンの状態の数で指数関数的です。これは、入力がNFAであるかDFAであるかに関係なく当てはまります。DFAの場合、入力オートマトンの反転の決定中に指数関数的爆発が発生する可能性が NFAの場合、入力オートマトンの初期決定中にも発生する可能性がただし、アルゴリズムは、この最悪の場合が示唆するよりもパフォーマンスが優れていることがよく

NFAの最小化
NFAの最小化
上記の手順はDFAに対しては機能しますが、分割の方法は非決定性有限オートマトン（NFA）に対しては機能しません。徹底的な検索はNFAを最小化する可能性がありますが、 P = PSPACEを除いて、一般的なNFAを最小化する多項式時間アルゴリズムはありません。ただし、ブルートフォース検索よりも効率的なNFA最小化の方法が

も参照してください
低電力の状態エンコーディング

ノート
^ Hopcroft、Motwani＆Ullman（2001）、セクション4.4.3、「DFAの最小化」。
^ Hopcroft＆Ullman（1979）、セクション3.4、定理3.10、p.67 ^ Hopcroft、Motwani＆Ullman（2001）、セクション4.4.3、「DFAの最小化」、p。159、およびp。164（定理4.26の後の注釈） ^ Xu、Yingjie（2009）。「決定性有限オートマトンの状態を最小化するためのnlognアルゴリズムの説明」。p。5 。
^ Knuutila（2001） ^ Berstel etal。（2011）。harvtxtエラー：ターゲットなし：CITEREFBerstelBoassonCartonFagnot2011（ヘルプ） ^ Knuutila（2001）の結果10に基づく ^ Hopcroft（1971） ; アホ、ホップクロフト＆ウルマン（1974） ^ デビッド（2012）。
^ Hopcroft、Motwani＆Ullman（2001）、セクション4.4、「NFAの状態の最小化」というラベルの付いた図、p。163。
^ Kameda＆Weiner（1970）。
^ Mに複数の最終状態がある場合、Mの反転で複数の初期状態を許可する必要がまたは、すべての初期状態にε遷移を含む追加の状態を追加し、この新しい状態のみを初期にします。
^ M ‘にはデッドステートがないことを思い出してしたがって、各州から少なくとも1つの単語が受け入れられます。
^ 州の言語は、その州から受け入れられた単語のセットです。
^ トリム=到達不能およびデッド状態を削除します。
^ たとえば、 n番目の記号が1であるバイナリ文字列の言語はn + 1状態のみを必要としますが、その反転には2n状態が必要です。Leiss（1981）は、反転に可能な最大数の2n状態を必要とする3値n状態DFAを提供しています。追加の例と、これらの例とBrzozowskiのアルゴリズムの最悪の場合の分析との関係の観察については、 Câmpeanuetal。を参照して（2001）。
^ 指数関数的爆発は、両方の決定ではなく、多くても1回だけ発生します。つまり、アルゴリズムは最悪の場合、二重指数関数ではなく指数関数になります。

参考文献
アホ、アルフレッドV。; ジョン・ホップクロフト; Ullman、Jeffrey D.（1974）、「4.13 Partitioning」、The Design and Analysis of Computer Algorithms、Addison-Wesley、pp。157–162。
ベルステル、ジャン; ボアソン、リュック; カートン、オリヴィエ; Fagnot、Isabelle（2010）、 “”Minimization of Automata”、Automata：from Mathematics to Applications、European Mathematical Society、arXiv：1010.5318、Bibcode：2010arXiv1010.5318B
Brzozowski、JA（1963）、「明確なイベントの正規正規表現と最小状態グラフ」、Proc。シンポジウム。算数。オートマトンの理論（ニューヨーク、1962年）、PolytechnicInst。のPolytechnicPress of Brooklyn、Brooklyn、NY、pp。529–561、MR 0175719。
Câmpeanu、Cezar; Culik、Karel、II; サロマ、カイ; Yu、Sheng（2001）、「有限言語の基本操作の状態の複雑さ」、第4回オートマタ実装に関する国際ワークショップ（WIA ’99）、コンピュータサイエンスのレクチャーノート、2214、Springer-Verlag、pp。60–70、doi：10.1007 / 3-540-45526-4_6、ISBN 978-3-540-42812-1。
David、Julien（2012）、「MooreとHopcroftのアルゴリズムの平均的な複雑さ」、Theoretical Computer Science、417：50–65、doi：10.1016 / j.tcs.2011.10.011。
Hopcroft、John（1971）、「有限オートマトンの状態を最小化するためのn log nアルゴリズム」、機械と計算の理論（Proc。Internat。Sympos。、Technion、Haifa、1971）、ニューヨーク：Academic Press、pp。 189〜196、MR 0403320。暫定版、テクニカルレポートSTAN-CS-71-190、スタンフォード大学、コンピュータサイエンス学部、1971年1月も参照して
ジョン・ホップクロフト; Ullman、Jeffrey D.（1979）、Automata理論、言語、および計算の概要、Reading / MA：Addison-Wesley、ISBN 978-0-201-02988-8
ジョン・ホップクロフト; モトワニ、ラジーブ; Ullman、Jeffrey D.（2001）、Automata Theory、Languages、およびComputationの概要（第2版）、Addison-Wesley。
亀田恒彦; Weiner、Peter（1970）、「非決定性有限オートマトンの状態最小化について」、IEEE Transactions on Computers、100（7）：617–627、doi：10.1109 / TC.1970.222994、S2CID 31188224。
Knuutila、Timo（2001）、「Hopcroftによるアルゴリズムの再記述」、Theoretical Computer Science、250（1–2）：333–363、doi：10.1016 / S0304-3975（99）00150-4、MR 1795249。
Leiss、Ernst（1981）、「ブールオートマトンによる正規言語の簡潔な表現」、Theoretical Computer Science、13（3）：323–330、doi：10.1016 / S0304-3975（81）80005-9、MR 0603263。
Leiss、Ernst（1985）、「ブールオートマトンIIによる正規言語の簡潔な表現」、理論計算機科学、38：133–136、doi：10.1016 / 0304-3975（85）90215-4
ムーア、エドワードF.（1956）、「思考実験-シーケンシャルマシンでの実験」、オートマタ研究、数学研究年報、no。34、プリンストン、NJ：プリンストン大学出版局、pp。129–153、MR 0078059。
Sakarovitch、Jacques（2009）、オートマトン理論の要素、 Reuben Thomasによるフランス語からの翻訳、ケンブリッジ大学出版局、ISBN 978-0-521-84425-3、Zbl 1188.68177

外部リンク
Myhill-Nerode定理を使用したDFA最小化”