※画像はイメージです。本文と直接の関係はありません
非決定性有限オートマトンから決定性有限オートマトンへの変換と最小化
1. 前提条件
本稿では、入力シンボルが 0 と 1 のみ で構成され、ε 遷移を一切持たない 非決定性有限オートマトン（NFA）を対象とします。
ε 遷移が存在する場合は、まず ε 閉包 を計算して ε 遷移を除去した NFA に対して以下の手順を適用してください。
2. NFA と DFA の基本的な違い
- 遷移の数
NFA では、同じ入力シンボルに対して遷移先が 0 個または複数個存在し得ますが、DFA では常に遷移先が 1 個に定まります。 - 初期状態
本稿では 1 つだけ（NFA・DFA 共通）とします。 - 受理状態
複数でも 0 個でも構いません。 - 遷移関数
NFA：δ : Q × Σ → 2^Q（状態集合）
DFA：δ : Q × Σ → Q（単一状態） - ε（空）遷移
本稿の対象では除外します。ε 遷移がある場合は、前述の通り ε 閉包を計算して除去してください。
3. 変換手順（5 ステップ）
ステップ 1 NFA の遷移表を作成する
各状態について入力シンボル 0 と 1 の遷移先集合を列挙します。
初期状態は矢印（→）で、受理状態はアスタリスク（＊）で示します。
ステップ 2 到達可能な部分集合だけを逐次生成する
幅優先探索（FIFO キュー）で実装すると分かりやすいです。以下は整形した擬似コードです。
未処理 ← { {q0} } // キューに初期集合だけを入れる
生成済 ← ∅ // すでに処理した集合の集合
while 未処理 ≠ ∅:
S ← 未処理から先頭要素を取り出す // キューから取り出す
生成済 ← 生成済 ∪ {S}
for a in {0, 1}:
T ← ⋃_{q∈S} δ_N(q, a) // NFA の遷移先集合の合併
if T = ∅:
// 空集合は死状態 φ として扱う
T ← φ
if T ∉ 生成済 かつ T ∉ 未処理:
未処理 ← 未処理 ∪ {T} // 重複を除いてキューに追加
この手順により、初期状態から到達可能な部分集合だけ が生成され、全 2^{|Q|} 個を列挙する必要はありません。
ステップ 3 DFA の遷移図を描く
ステップ 2 で得た各集合を DFA の 1 つの状態とみなします。
- 受理状態の決定
NFA の受理状態を 1 つでも含む集合は、DFA においても受理状態となります。 - 死状態 φ の扱い
空集合は φ と表記し、全シンボルに対して自己遷移だけを持つ唯一の死状態とします。φ は決して受理状態にしません。
NFA のある状態で特定のシンボルに対する遷移が定義されていない（遷移先集合が空）場合にのみ φ が現れます。未定義遷移はすべて φ に遷移させることで、遷移表が完全になります。
ステップ 4 到達不可能な状態の削除
初期状態から辿れない DFA の状態はすべて削除し、残った状態と遷移だけでオートマトンを構成します。
この削除は 最小化を行う前提条件 であり、削除し忘れると最小化の結果が正しくならない可能性があります。ステップ 2 で到達可能な集合だけを生成すれば理論上は不要ですが、手作業で遷移図を描く際のミス防止のために残しておくと教育的です。
ステップ 5 DFA の最小化（等価状態の統合）
本手順は Myhill–Nerode 等価関係 に基づく状態分割法（通称：分割法）を用います。
（同様の手法は「ホップクロフトのアルゴリズム（簡易版）」とも呼ばれます。）
- 初期分割
受理状態集合と非受理状態集合に分けます。死状態 φ が存在する場合は、非受理状態集合に含めます。 - 等価状態の直感的説明
「ある状態からどのような文字列を入力しても、受理になるか非受理になるかの結果が全く同じである状態同士」を等価と呼びます。等価な状態は互いに置き換えても言語の受理性は変わりません。 - 分割の繰り返し
各クラスについてシンボル 0、1 の遷移先が同一クラスに属しているかを確認します。遷移先が φ になる場合も、φ はひとつのクラスとして扱います。条件を満たさない状態は新しいクラスに分割します。 - 安定化の判定
前回の分割と比較し、分割が変化しなくなったとき（全クラスが安定したとき）にアルゴリズムを終了します。 - 統合
同一クラスに属する状態を 1 つに統合し、最小 DFA を完成させます。
この手順は「受理・非受理の区別」と「遷移先が同一クラスに属するか」の両方を基準にしているため、正しく最小化された DFA が得られます。
4. 変換のポイントとコツ（Tips）
- 状態数の上限
NFA が n 個の状態を持つとき、DFA の状態数は理論上最大で 2ⁿ 個 になります。最悪ケースではすべての部分集合が到達可能になることもありますが、実務上は「到達可能な部分集合だけ」を生成すれば、実際に必要な状態数は 2ⁿ 未満になることが多いです。 - 死状態 φ の扱い
未定義遷移はすべて φ に遷移させ、φ は全シンボルで自己遷移を持つ死状態とします。φ は決して受理状態にしません。 - 遷移表作成と同時チェック
新しい集合が出たらすぐに表に追記し、抜けがないか確認します。 - 最小化の条件
受理状態か否かが同じで、かつすべての入力シンボルに対する遷移先が同一クラスに属する場合にのみ、状態を統合できます。 - ε 遷移の除外について
本稿は ε 遷移を持たない NFA を対象としています。ε 遷移があるオートマトンを扱う場合は、先に ε 閉包 を計算してから本手順に入ることを忘れないでください。
5. まとめ（チェックリスト）
- 前提条件（シンボルは 0,1 のみ、ε 遷移はなし）を満たす NFA は、部分集合構成法に従えば必ず等価な DFA に変換できる。
- 到達可能な部分集合だけを生成すれば、実務上は状態数が 2ⁿ 未満になることが多く、計算コストを抑えられる。
- 到達不可能な状態は最小化の前に必ず削除し、残った状態で Myhill–Nerode（＝ホップクロフト）分割法を適用すれば、最小 DFA が得られる。
- 死状態 φ は全シンボルで自己遷移し、受理状態にしないことを徹底すれば、未定義遷移の扱いに困りません。
- ε 遷移がある場合は事前に ε 閉包 を取ることで、手順全体を安全に実行できる。
この手順を紙とペンで実際に試すことで、NFA → DFA 変換と最小化の流れを確実に身につけられるはずです。
