非決定性オートマトン（NFA）を決定性オートマトン（DFA）へ変換する手順と実装例
用語一覧
- Φ … 空集合
- ε … 空文字（ε 遷移）
- TRAP 状態（ゴミ箱状態） … 未定義遷移をまとめて表す特別な状態
1. NFA と DFA の基本定義（復習）
NFA（非決定性有限オートマトン）
- 同一入力記号に対して遷移先が 0 個以上存在できる。
- 本稿では開始状態は 1 つだけと仮定する。
- 開始状態が複数ある場合は、すべての開始状態へ ε 遷移でつながる新たな開始状態 s₀ を作り、s₀ を唯一の開始状態とする。元の NFA が ε を受理する場合は、s₀ を受理状態に加えても言語は変わらない。
DFA（決定性有限オートマトン）
- 各状態からすべての入力記号に対して遷移先が必ず 1 つに決まっている。
- 未定義の遷移は TRAP 状態 に遷移させて表現できる（TRAP 状態は省略可能で、未定義遷移が出た時点で「拒否」と判定しても言語は変わらない）。
この違いを埋める手法が 部分集合構成法（subset construction） である。
2. 変換手順（5 段階）
2.1 状態遷移表の作成
NFA の全状態と全入力記号について、遷移先集合（空集合は Φ）を書き出す。
2.2 開始集合の ε 閉包計算
開始状態 q₀ から ε 遷移で到達できるすべての状態を再帰的に加えた集合
[
\varepsilon\text{-closure}({q₀})
]
を DFA の開始集合とする。
2.3 部分集合構成による DFA の遷移表作成
- DFA の各状態は NFA の状態集合になる。
- 任意の集合
Sと入力記号aについて次の手順で次状態Tを求める。Sの各状態がaで遷移できる集合T₁を列挙する。T₁に対して ε 閉包 を計算し、得られた集合Tを DFA の次状態とする。Tが空集合（Φ）のときは、遷移先を TRAP 状態 とする。Tが新たに出現した集合であれば遷移表に追加し、すべての集合が処理されるまで繰り返す。2.4 受理状態集合の決定
DFA の各状態（＝状態集合）について、元 NFA の受理状態が 少なくとも 1 つ 含まれていればその集合を DFA の受理状態に加える。ε 閉包後の集合でも同様に判定する。なお、受理状態は 開始集合から到達可能な集合 のみを対象とする。
2.5 DFA の構築完了
上記で得られた遷移表が NFA と等価な DFA になる。必要に応じて最小化を別工程で行う。
3. ε 閉包の計算手順（実装ヒント）
- 初期集合に ε 遷移先をすべて加える。
- 追加された状態について再帰的に同様の操作を繰り返す。
- 集合に変化がなくなるまで続ける。
実装上は スタック または キュー を用いた幅優先探索が安全で、スタックオーバーフローや無限ループを防げる。
4. 具体例：NFA
M₁の変換
4‑1. NFA の定義
- 状態集合
Q = { q₀, q₁, q₂ } - 入力記号
Σ = { 0, 1 } - 遷移関数
q₀–0→{ q₀ }q₀–ε→{ q₁ }q₁–0→{ q₂ }q₁–1→{ q₁ }q₂–0→{ q₂ }q₂–1→{ q₀ }
- 開始状態
q₀、受理状態集合F = { q₂ }4‑2. 初期集合と ε 閉包
開始集合 { q₀ } に ε で到達できる q₁ を加えると
\varepsilon\text{-closure}({q₀}) = { q₀, q₁ }
q₁ からはさらに ε 遷移が無いため、ここで計算は完了する。
4‑3. 部分集合構成による遷移表（集合表記）
・{ q₀, q₁ }：q₀ --0--> { q₀ }、q₁ --0--> { q₂ } → 合併 { q₀, q₂ } → ε‑閉包 → { q₀, q₁, q₂ }
・{ q₀, q₁, q₂ }：q₀ --0--> { q₀ }、q₁ --0--> { q₂ }、q₂ --0--> { q₂ } → 合併 { q₀, q₂ } → ε‑閉包 → { q₀, q₁, q₂ }（同じ集合）
・{ q₁ }：q₁ --0--> { q₂ } → ε‑閉包 → { q₀, q₁, q₂ }
・Φ（TRAP）：0, 1 いずれも Φ
※ { q₀, q₁ } から入力 1 の遷移は { q₁ } になる点に注意。q₀ には 1 の遷移が無く、ε 閉包は { q₁ } のみである。
4‑4. 受理状態集合の決定
到達可能な DFA の状態集合は次の 3 つである。
- { q₀, q₁ }（開始集合）
- { q₀, q₁, q₂ }（0 を読んだ結果）
- { q₁ }（1 を読んだ結果）
このうち 元 NFA の受理状態 q₂ を含む集合は { q₀, q₁, q₂ } だけ である。したがって
F_{\text{DFA}} = { { q₀, q₁, q₂ } }
この DFA は元の NFA と同じ言語を認識する。
5. DFA の最小化（分割法）
- 到達不可能状態の除去 初期状態から辿れない状態は最小化の対象外とする。BFS などで到達可能な集合だけを抽出する。
- 初期分割 到達可能な状態を「受理状態」と「非受理状態」に分ける。
- 分割の繰り返し 同一クラス内の各状態について、同じ入力記号に対する遷移先が同一クラスに属しているかを確認し、条件を満たさない状態があればクラスを分割する。
- 安定化まで繰り返す クラス分割がこれ以上変化しなくなる（安定する）まで 3 を繰り返す。
最小 DFA の構築 安定したクラスをそれぞれ 1 つの状態としてまとめ、遷移表を再構成すれば最小 DFA が得られる。
6. 実装例：C 言語での DFA シミュレータ
状態の定義 列挙型で DFA の状態を列挙し、未定義遷移用に
TRAPを追加する。- 遷移表の記述
状態数と入力記号数が増えても拡張しやすいように、
int transition[NUM_STATE][NUM_SYMBOL]の二次元配列で遷移表を保持する。 - 受理判定 入力文字列をすべて読み終えた後、現在の状態が受理状態集合に属しているかをチェックする。途中で受理状態に入っても、残り文字がある限り判定は保留される。
- TRAP 状態の扱い
- 方式 A（遷移後は TRAP に留まる）：未定義遷移が出たら即座に
TRAPに遷移させ、以降は入力を読み続けても状態は変わらない。 - 方式 B（未定義遷移で即座に拒否）：未定義遷移が出た時点でシミュレーションを終了し、残り文字があっても「拒否（非受理）」と判定する。
どちらを選んでも認識言語は変わらないが、途中での遷移情報が必要かどうかで選択基準が変わる。用途に応じて適切な方式を採用すればよい。
> 読者へのヒント
> - 手計算で DFA 変換を行うコツ：まず開始状態の ε‑閉包を求め、そこから「部分集合構成法」を順に適用して新しい集合を探索していくと漏れがなくなる。
> - 最小化で忘れがちな点：TRAP 状態（死状態）も 1 つのクラスとして扱うことを忘れない。全ての入力に対して自分自身に遷移させる非受理状態として扱えば、分割法が正しく機能する。
7. まとめ
- 方式 A（遷移後は TRAP に留まる）：未定義遷移が出たら即座に
- NFA と DFA の根本的な違いは遷移の一意性にある。
- 変換は次の 5 手順で体系的に行える。
- 状態遷移表作成
- 開始集合の ε 閉包
- 部分集合構成（各遷移ごとに必ず ε 閉包を適用）
- 受理状態集合の決定（到達可能な集合だけを対象）
- DFA 構築完了
- ε 閉包は開始集合だけでなく、すべての入力シンボルごとの遷移計算のたびに必ず適用する必要がある。例として
{q₀,q₁}が0を読むとき、まず{q₀,q₂}を得て、そこに ε 閉包を取って{q₀,q₁,q₂}になる手順が典型的である。 - 受理状態は、ε 閉包後の状態集合に元 NFA の受理状態が含まれるかで判定する。
- DFA の最小化は 到達不可能状態を除去した後に分割法を適用 するのが標準的で、計算量を削減できる。
- C 言語実装は列挙型と二次元遷移配列でシンプルに記述でき、TRAP 状態の扱いは方式 A か方式 B を選べば柔軟に対応できる。 本手順を身につければ、大学の課題はもちろん、研究や実務でオートマトンをプログラムに組み込む際にもスムーズに対応できる。変換表を書き留めて、実装に活用しましょう。
