DFAの最小化

オートマトン理論（理論計算機科学の一分野）において、 DFA最小化とは、与えられた決定性有限オートマトン（DFA）を、状態数が最小の同等のDFAに変換する作業である。ここで、2つのDFAは同じ正規言語を認識する場合、同等であると言われる。この作業を実行するいくつかの異なるアルゴリズムが知られており、オートマトン理論の標準的な教科書に記載されている。^[1]

各正規言語には、それを受け入れる最小のオートマトン、つまり状態数が最小のDFAも存在し、このDFAは一意です（ただし、状態に異なる名前を付けることができる点が異なります）。 ^{[2] [3]最小のDFAは、}パターンマッチングなどのタスクの計算コストを最小限に抑えます。

受け入れる言語に影響を与えずに、元の DFA から削除またはマージできる状態には 3 つのクラスがあります。

• 到達不能状態は、どの入力文字列に対しても DFA の初期状態から到達できない状態です。これらの状態は削除できます。
• デッド状態とは、最終状態に到達できない状態です。オートマトンが完全である必要がない限り、これらの状態は削除できます。
• 区別不可能な状態とは、どの入力文字列に対しても互いに区別できない状態です。これらの状態は結合できます。

DFA の最小化は通常、次の 3 つのステップで実行されます。

1. デッド状態と到達不能状態を削除します（これにより次のステップが高速化されます）。
2. 区別できない状態を統合する、
3. 結果の DFA が完了する必要がある場合は、オプションで単一のデッド状態 (「シンク」状態) を再作成します。

決定性有限オートマトンの状態は、となる文字列が に存在しない場合に到達不可能です。この定義では、は状態の集合、は入力記号の集合、は遷移関数（状態と入力記号を状態の集合にマッピングする）、はその文字列への拡張（拡張遷移関数とも呼ばれる）、は初期状態、 は受け入れ（最終）状態の集合です。到達可能な状態は、次のアルゴリズムで取得できます。 ${\displaystyle p}$${\displaystyle M=(Q,\Sigma ,\delta ,q_{0},F)}$${\displaystyle w}$${\displaystyle \Sigma ^{*}}$${\displaystyle p=\delta ^{*}(q_{0},w)}$${\displaystyle Q}$${\displaystyle \Sigma }$${\displaystyle \delta }$${\displaystyle \delta ^{*}}$${\displaystyle q_{0}}$${\displaystyle F}$

 到達可能な状態 :=  { q0 }
とし、新しい状態:= { q0 }とします。   

do  { 
    temp  := 空 集合new_statesの各qに対してdo Σの各cに対してdo temp := temp ∪ { δ ( q , c )} new_states : = temp \ reachable_states reachable_states :  = reachable_states ∪ new_states } while ( new_states ≠空集合)
         
             
                
        
        
      

到達不可能な状態 :=  Q  \ 到達可能な状態

状態セット（例：new_states）とそれに対する操作（状態の追加や状態が存在するかどうかの確認など）の効率的な実装を前提とすると、このアルゴリズムは時間計算量 で実装できます。ここで、は状態の数、 は入力オートマトンにおける遷移の数です。 ${\displaystyle O(n+m)}$${\displaystyle n}$${\displaystyle m}$

到達不能な状態は、受け入れる言語に影響を与えることなく、DFA から削除できます。

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

Hopcroft (1971) による、DFA の区別できない状態をマージするアルゴリズムの 1 つは、パーティション リファインメントに基づいており、DFA 状態をその動作によってグループに分割します。これらのグループはNerode 合同の同値類を表します。これにより、2 つの状態はすべて、すべての入力シーケンスに対して同じ動作をする場合、同等になります。つまり、パーティションPの同じブロックに属する2 つの状態p ₁とp ₂とすべての入力ワードwごとに、 wによって決定される遷移は、常に状態p ₁とp ₂を、両方が受け入れる状態または両方が拒否する状態に移行させる必要があります。wがp _{1 を}受け入れ状態にし、p _{2 を}拒否状態に したり、その逆を行ったりすることはできません。

以下の疑似コードは、Xuによって与えられたアルゴリズムの形式を記述したものです。^[4] 代替形式も提示されています。^{[5] [6]}

P  :=  { F ,  Q  \  F } 
W  :=  { F ,  Q  \  F }

 ( W が 空でない )場合、Σの各cについてWから集合A を選択して削除します。Xを、c上の遷移がAの状態につながる状態の集合とします。Pの各集合Yで、X ∩ Yが空でなく、Y \ Xが空でない場合に、YがW にある場合はPのY を2つの集合X ∩ YとY \ Xで置き換えます。YがWにある場合はWのY を同じ2 つの集合で置き換えます。それ以外の場合は| X ∩ Y | <= | Y \ X |の場合、 X ∩ YをWに追加します。それ以外の場合はY \ X をWに追加します。 
           
         
                          
                           
                          
                
                        
            
                       
                         
                
                         

アルゴリズムは、粗すぎる分割から始まります。つまり、ネロード合同に従って同等であるすべての状態のペアは、分割内の同じセットに属しますが、同等でないペアも同じセットに属する可能性があります。分割は徐々に多数の小さなセットに細分化され、各ステップで状態セットが必然的に同等でないサブセットのペアに分割されます。最初の分割は、状態を、明らかに互いに同じ動作をしない 2 つの状態のサブセット (受け入れ状態と拒否状態) に分離したものです。次に、アルゴリズムは、現在の分割からセットAと入力シンボルc を繰り返し選択し、分割の各セットを 2 つの (空の可能性のある) サブセット (入力シンボルcでAにつながる状態のサブセットと、 Aにつながらない状態のサブセット)に分割します。A はパーティションの他のセットとは異なる動作をすることが既にわかっているため、 AにつながるサブセットもAにつながらないサブセットとは異なる動作をします。このタイプの分割がこれ以上見つからない場合、アルゴリズムは終了します。

補題. 固定された特性cと同値類Yが同値類BとCに分割されると、分割全体を精緻化するために必要なのはBかCのどちらか一方だけである。 ^[7]

例: 同値クラスYがあり、それが同値クラスBとCに分割されるとします。また、クラスD、E、F があるとします。DとE は文字cでBに遷移する状態を持ち、F は文字cでCに遷移します。補題により、BまたはCのいずれかを識別子として選択できます。たとえば、Bとします。すると、 DとEの状態は、 Bへの遷移によって分割されます。ただし、 Bを指していないFは、アルゴリズムの現在の反復処理では分割されず、他の識別子によって調整されます。

観察。 D、E、Fなどの参照クラスを正しく分割するには、 BまたはCのすべてが必要です。サブセットでは不十分です。

if最も外側のステートメント ( )の目的は、識別子のセットであるW をif Y is in W修正することです。アルゴリズムの前のステートメントで、Yが分割されたことがわかります。YがWにある場合、それは将来の反復でクラスを分割する手段としては古くなったばかりです。したがって、上記の観察により、Y は両方の分割で置き換えられる必要があります。ただし、 Y がWにない場合は、上記の補題により、 2 つの分割のうち両方ではなく、どちらか一方のみをWに追加する必要があります。 2 つの分割のうち小さい方を選択すると、Wへの新しい追加がYの半分のサイズ以下になることが保証されます。これがホップクロフト アルゴリズムの核心であり、次の段落で説明するように、どのように速度を上げるかです。

このアルゴリズムの最悪ケースの実行時間はO ( ns log n )です。ここで、nは状態の数、s はアルファベットのサイズです。この制限は、オートマトンの各ns遷移について、遷移のターゲット状態を含むQから抽出されたセットのサイズが互いに 2 倍以上減少するという事実から導かれます。そのため、各遷移はアルゴリズムの分割ステップのO (log n )回に参加します。パーティション リファインメントデータ構造により、各分割ステップは、参加する遷移の数に比例した時間で実行できます。^[8]これは、問題を解決するための最も効率的なアルゴリズムとして知られており、特定の入力分布では、平均ケースの複雑さはさらに優れており、O ( n log log n )です。^[6]

ホップクロフトのアルゴリズムを使用して入力 DFA の状態を同値クラスにグループ化すると、各同値クラスに対して 1 つの状態を形成することによって最小 DFA を構築できます。SがPの状態セット、sがSの状態、c が入力文字である場合、入力 cでのSの状態からの最小 DFA の遷移は、入力cで状態sから入力オートマトンが遷移する状態を含むセットに移動します。最小 DFA の初期状態は、入力 DFA の初期状態を含む状態であり、最小 DFA の受け入れ状態は、メンバーが入力 DFA の受け入れ状態である状態です。

DFA 最小化のためのムーアのアルゴリズムは、エドワード F. ムーア(1956)によるものです 。ホップクロフトのアルゴリズムと同様に、このアルゴリズムは、受け入れ状態と拒否状態を分離することから始まるパーティションを維持し、それ以上の改良ができなくなるまでパーティションを繰り返し改良します。各ステップで、現在のパーティションをs + 1パーティションの最も粗い共通改良に置き換えます。そのうちの 1 つは現在のパーティションで、残りは各入力シンボルの遷移関数による現在のパーティションの原像です。この置き換えによって現在のパーティションが変更されない場合、アルゴリズムは終了します。最悪の場合の時間計算量はO ( n ² s )です。アルゴリズムの各ステップは、基数ソートのバリアントを使用して状態を並べ替え、新しいパーティションの同じセット内の状態が順序で連続するようにすることで、時間O ( ns )で実行できます。最後のステップを除く各ステップでパーティション内のセットの数が増えるため、ステップ数は最大でnです。 DFA最小化問題で最悪のケースの動作を引き起こす例は、ホップクロフトのアルゴリズムの場合と同じです。アルゴリズムが実行するステップ数はnよりもはるかに小さいため、平均すると（定数sの場合）、アルゴリズムの平均ケースの動作をモデル化するために選択されたオートマトン上のランダム分布に応じて、そのパフォーマンスはO（n log n）またはO（n log log n）になります。 ^{[6] [9]}

非決定性有限オートマトン(NFA)の遷移を反転し、初期状態と最終状態を切り替えると^{[注 1]、}元の言語の反転に対するNFA が生成されます。この NFA を標準のべき集合構築を使用して DFA に変換すると(変換された DFA の到達可能な状態のみを保持)、同じ反転言語の DFA が生成されます。Brzozowski (1963) が観察したように、この反転と決定化をもう一度繰り返し、到達可能な状態のみを保持すると、元の言語の最小の DFA が生成されます。 ${\displaystyle M}$${\displaystyle M^{R}}$${\displaystyle M_{D}^{R}}$

アルゴリズムの背後にある直感は次のとおりです。逆オートマトンを決定化すると、元のオートマトンでは区別できない状態がマージされますが、複数の受け入れ状態が生成される場合があります。このような場合、オートマトンを 2 回目に反転すると、これらの受け入れ状態が初期状態になり、複数の初期状態があるためにオートマトンが決定論的でなくなります。そのため、最小の DFA を取得するには、再度決定化する必要があります。

を決定化してを取得した後、これを逆にしてを取得します。 はと同じ言語を認識しますが、重要な違いが 1 つあります。 には、同じ単語を受け入れることができる 2 つの状態はありません。これは が決定論的であることから生じます。つまり、 では、初期状態から同じ単語を介して到達できる 2 つの状態はありません。 を決定化すると、べき乗状態 ( の状態セット) が作成されます。この場合、2 つのべき乗状態は、の少なくとも 1 つの状態において ‒ 当然 ‒ 異なります。 およびと仮定すると、 はの言語に少なくとも 1 つの単語^{[注 2]を追加します[注 3]。}この単語は に固有であるため (他のどの状態も受け入れません)、 には存在し得ません。 これはべき乗状態の各ペアに当てはまり、したがって各べき乗状態は他のすべてのべき乗状態と区別できることがわかります。 したがって、 を決定化した後、区別できない状態や到達できない状態のない DFA が得られます。これが、元の の最小の DFA です。 ${\displaystyle M^{R}}$${\displaystyle M_{D}^{R}}$${\displaystyle M_{D}^{R}}$${\displaystyle (M_{D}^{R})^{R}=M'}$${\displaystyle M'}$${\displaystyle M}$${\displaystyle M'}$${\displaystyle M_{D}^{R}}$${\displaystyle M_{D}^{R}}$${\displaystyle M'}$${\displaystyle M'}$${\displaystyle {\mathcal {R}},{\mathcal {S}}}$${\displaystyle q}$${\displaystyle M'}$${\displaystyle q\in {\mathcal {R}}}$${\displaystyle q\not \in {\mathcal {S}}}$${\displaystyle q}$${\displaystyle {\mathcal {R}}}$${\displaystyle {\mathcal {S}}}$${\displaystyle q}$${\displaystyle M'}$${\displaystyle {\overline {M}}}$${\displaystyle M}$

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

上記の手順はDFAには有効ですが、分割法は非決定性有限オートマトン（NFA）には有効ではありません。^{[10]網羅的な探索によってNFAを最小化できるかもしれませんが、} P = PSPACEでない限り、一般的なNFAを最小化する多項式時間アルゴリズムは存在しません。これは計算複雑性理論における未解決の予想であり、広く誤りであると信じられています。ただし、 NFAを最小化する方法は、総当たり探索よりも効率的である可能性があります。^[11]

• 低消費電力のための状態エンコーディング

• Aho, Alfred V. ; Hopcroft, John E. ; Ullman, Jeffrey D. (1974)、「4.13 パーティショニング」、The Design and Analysis of Computer Algorithms、Addison-Wesley、pp. 157–162。
• Berstel, Jean; Boasson, Luc; Carton, Olivier; Fagnot, Isabelle (2010)、「オートマトン最小化」、Automata: from Mathematics to Applications、欧州数学会、arXiv : 1010.5318、Bibcode :2010arXiv1010.5318B
• Brzozowski, JA (1963)、「明確なイベントに対する正規正規表現と最小状態グラフ」、Proc. Sympos. Math. Theory of Automata (ニューヨーク、1962)、Polytechnic Press of Polytechnic Inst. of Brooklyn、ブルックリン、ニューヨーク、pp. 529–561、MR  0175719。
• Câmpeanu, Cezar; Culik, Karel II; Salomaa, Kai; Yu, Sheng (2001)、「有限言語における基本演算の状態複雑度」、オートマタ実装、コンピュータサイエンスの講義ノート、vol. 2214、Springer-Verlag、pp. 60–70、doi :10.1007/3-540-45526-4_6、ISBN 978-3-540-42812-1。
• デイビッド、ジュリアン (2012)、「ムーアとホップクロフトのアルゴリズムの平均複雑性」、理論計算機科学、417 :50–65、doi : 10.1016/j.tcs.2011.10.011。
• ホップクロフト、ジョン(1971)、「有限オートマトンの状態を最小化するn log nアルゴリズム」、機械と計算の理論 (Proc. Internat. Sympos.、テクニオン、ハイファ、1971)、ニューヨーク: アカデミック プレス、pp. 189–196、MR  0403320スタンフォード大学コンピュータサイエンス学部の技術レポート STAN-CS-71-190、1971 年 1 月の暫定版も参照してください。
• ホップクロフト、ジョン E.; ウルマン、ジェフリー D. (1979)、『オートマトン理論、言語、計算入門』、Reading/MA: Addison-Wesley、ISBN 978-0-201-02988-8
• ホップクロフト、ジョン E. ;モトワニ、ラジーブ;ウルマン、ジェフリー D. (2001)、『オートマトン理論、言語、計算入門(第 2 版)』、アディソン ウェズリー。
• 亀田恒彦、ピーター・ワイナー（1970）「非決定性有限オートマトンの状態最小化について」IEEE Transactions on Computers、100（7）：617–627、doi：10.1109/TC.1970.222994、S2CID  31188224。
• クヌーティラ、ティモ (2001)、「ホップクロフトによるアルゴリズムの再記述」、理論計算機科学、250 (1–2): 333–363、doi :10.1016/S0304-3975(99)00150-4、MR  1795249。
• Leiss, Ernst (1981)、「ブールオートマトンによる正規言語の簡潔な表現」、理論計算機科学、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)、「順序機械に関するゲダンケン実験」、オートマトン研究、数学研究年報、第 34 号、プリンストン、ニュージャージー: プリンストン大学出版局、pp. 129–153、MR  0078059。
• サカロヴィッチ、ジャック（2009）、オートマトン理論の要素、フランス語からルーベン・トーマス訳、ケンブリッジ大学出版局、ISBN 978-0-521-84425-3、Zbl  1188.68177

• マイヒル・ネロード定理を用いたDFA最小化