DFAの最小化・等価性

決定性有限オートマトンの不要な状態を整理し、2つの受理言語が同一か確認する。

DFAのみを扱います。1つの状態・記号の組に遷移先を複数指定することはできません。

未記載の遷移は非受理のsinkへ補完します。比較では同じアルファベットを2つのDFAに適用します。

項目を入力・選択してから「計算する」を押してください。

選択内容に応じて、残りの入力項目を案内します。

計算する内容
アルファベット(共通の入力記号)任意
行記号 任意操作
1

1列を左端の欄へタブ区切りで貼り付けられます。12行まで。

各行に空白以外の1文字。0・1なども文字として扱います。全行空欄なら空アルファベット(Σ=∅)です。記号の並び順は最短反例の優先順です。

DFA A:状態と初期・受理の指定必須
行状態名初期受理操作
1

3列を左端の欄へタブ区切りで貼り付けられます。60行まで。

初期状態はちょうど1件。「受理」は各状態について選択してください。状態名には英数字と . _ : - が使えます。

DFA A:遷移表任意
行遷移元 任意記号 任意遷移先 任意操作
1

3列を左端の欄へタブ区切りで貼り付けられます。720行まで。

遷移元・記号・遷移先を1行ずつ指定。記載のない組は非受理のsink状態へ補完します。空行は遷移の指定なしとして扱います。


計算結果

値を入力して計算してください。

お気に入り一覧

計算方法・適用範囲・出典

計算方法

初期状態からの到達可能状態を求め、未定義の遷移は非受理sinkへの辺で補完します。受理・非受理の分割から始め、各記号に対する遷移先の同値類が一致する状態をまとめる分割細分化を、変化がなくなるまで反復します。2つのDFAは初期状態対から積オートマトンを幅優先探索し、受理性が異なる最初の状態対への入力列を最短の区別語とします。初期状態の受理性が違えば反例は空語εです。

最小DFAの同値類と遷移表、到達不能状態、2言語の等価性と最短区別語。

計算例(架空の数値)

資料の例:状態1〜9、記号a・b、初期1、受理2・3・5について、同値類{1,4,7}と{3,5}を統合すると最小DFAは6状態になります。

適用対象と限界

定義済みの状態名・初期状態・受理状態・有限アルファベットを持つDFA。NFA、ε遷移、正規表現の自動変換、重み付きオートマトン、無限状態、遷移の複数候補は対象外。

採用した方式

  • DFAの同値類による最小化と積オートマトンBFS(E1182 v1.0):対象範囲 決定性、記号は空白以外のUnicode 1文字。未定義遷移を非受理sinkで補完。最大60状態/機械・12記号/適用地域 global

方法と出典

方法:E1182 v1.0(2026-11-14)。データ記録日:2026-11-14。