DFAの最小化・等価性
バグ・不具合を報告
決定性有限オートマトンの不要な状態を整理し、2つの受理言語が同一か確認する。
DFAのみを扱います。1つの状態・記号の組に遷移先を複数指定することはできません。
未記載の遷移は非受理のsinkへ補完します。比較では同じアルファベットを2つのDFAに適用します。
項目を入力・選択してから「計算する」を押してください。
選択内容に応じて、残りの入力項目を案内します。
計算結果
—
- DFA Aの最小状態数
- —
- 受理言語の等価性
- —
- 最短の区別語(反例)
- —
- DFA Bの最小状態数
- —
- DFA Aの到達可能状態数(補完前)
- —
- DFA Aの到達不能状態数
- —
値を入力して計算してください。
この計算機は使いやすかったですか?
回答はサイト改善のために保存します。入力値・計算結果は送りません。
ありがとうございます。よかったら、上の共有ボタンからこの計算機を紹介しませんか?
計算方法・適用範囲・出典
計算方法
初期状態からの到達可能状態を求め、未定義の遷移は非受理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。