非決定性オートマトン（NFA）を決定性オートマトン（DFA）に変換する手順
1. NFA と DFA の基本的な違い
- 遷移の形：同じ入力シンボルに対して 複数 の矢印が出てもよい。遷移が 0 本 でも構わない。
- 開始状態：開始状態は 1 つ とし、ε遷移を許すことで実質的に複数の開始状態を表現できる。
- 記述の直感性：複数の道が同時に走るイメージで、直感的に書きやすい。
- 受理判定：入力全体を読んだとき、到達可能な状態集合の中に受理状態があれば受理 になる。
2. 変換手順（全体像）
NFA の遷移表を作成
各状態と入力シンボルに対する遷移先集合を表にまとめる。開始状態集合の決定
- 初期状態は NFA の開始状態だけを含む集合
{開始状態}。 - ε遷移がある場合は、その開始状態の ε閉包（その状態から ε 遷移だけで到達できるすべての状態の集合）を取ってから集合化する。
- 本例では ε遷移が無いため、開始集合はそのまま
{q₀}になる。
- 初期状態は NFA の開始状態だけを含む集合
状態集合ごとの遷移先を求める
現在の状態集合に含まれるすべての NFA の遷移先集合を 合併 し、ε遷移がある場合は その合併結果全体の ε閉包 を取る。これが次の DFA の状態（＝状態集合）になる。空集合（φ）を死状態として導入
遷移先が空集合になる場合は、唯一の死状態 φ として扱う。φ からはすべての入力で再び φ へ遷移させ、完全に定義された DFA を作る。受理状態の決定
DFA の各状態集合に NFA の受理状態が 1 つでも含まれていれば その集合は受理状態になる。ε遷移がある場合は、ε閉包を取った後の集合でも同様に判定する。（任意）最小化
- まず 受理状態と非受理状態に分けて初期分割 を行う。
- その後、すべての入力シンボルに対して遷移先が同じグループに属しているか を調べ、同じであれば同一グループに統合する（分割法）。
- 必要に応じて分割を繰り返し、等価な状態がすべて統合されたときが最小 DFA である。
3. 例題で手順を確認する
3‑1. 例題の NFA（図の代替説明）
以下の遷移を持つ NFA を考える（Mermaid 記法で描くと見やすくなる）。
- 状態：
q₀、q₁ - 開始状態：
q₀ - 受理状態：
q₁ - 遷移
q₀が入力 a のとき{q₀, q₁}へ遷移q₀が入力 b のとき{q₀}へ遷移q₁が入力 a のとき{q₁}へ遷移q₁が入力 b のとき 遷移なし（空集合 φ）
注：ここでの「φ」は「遷移先が存在しない」ことを示す記号であり、DFA では 死状態 として扱う。
3‑2. ステップ 1 ― NFA の遷移表
・q₀：{q₀, q₁} ・q₁：{q₁}
3‑3. ステップ 2・3 ― 状態集合の生成と遷移先の計算
開始集合は {q₀}（ε遷移なし）。
各集合に対して a, b の遷移先を合併し、必要なら ε閉包を取って次の集合を得る。
・{q₀}：{q₀, q₁}
・{q₀, q₁}：{q₀, q₁}
・φ：φ
a を入力したとき
{q₀}→{q₀, q₁}（q₀ の a が{q₀, q₁}）{q₀, q₁}→{q₀, q₁}（q₀ の a が{q₀, q₁}、q₁ の a が{q₁}、合併すると同じ集合）
b を入力したとき
{q₀}→{q₀}（q₀ の b が{q₀}）{q₀, q₁}→{q₀}（q₀ の b が{q₀}、q₁ の b が φ、合併すると{q₀}）
3‑4. ステップ 4 ― 完成した DFA の遷移表
・{q₀}：{q₀, q₁} ・{q₀, q₁}：{q₀, q₁} ・φ：φ
3‑5. ステップ 5 ― 死状態（φ）の取り扱い
φ は唯一の死状態として扱う。φ からはすべての入力で再び φ へ遷移するだけである。
この例では、q₁ が入力 b を受け取ると φ に到達するため、実際に φ が利用されるケースがある。完全に定義された DFA を作る際には、必ず φ を用意しておくことが重要である。
3‑6. ステップ 6 ― 受理状態の決定
NFA の受理状態は q₁ である。
- {q₀, q₁} に q₁ が含まれるので受理状態になる。
- {q₀} と φ には q₁ が含まれないため非受理状態となる。
3‑7. ステップ 7 ― 最小化（任意）
- 初期分割：受理状態を含む集合
{q₀, q₁}とそれ以外{q₀}、φ に分ける。 - 同一遷移の確認：
{q₀}と{q₀, q₁}は a に対する遷移先が同じ{q₀, q₁}だが、受理性が異なるため統合できない。- φ は死状態であり、他の状態と遷移パターンが一致しないのでそのまま残す。
この例では最小化を行っても状態数は変わらない。
4. 変換チェックリスト（要点まとめ）
- NFA の遷移表は正確に
- 各状態・入力シンボルに対する遷移先集合（φ も含む）で記述する。
- 開始状態集合は
{開始状態}（ε閉包が必要ならその結果） - 遷移先は「現在の状態集合に含まれるすべての状態の遷移先集合を合併し、必要なら ε閉包を取る」
- 空集合 φ は唯一の死状態として扱う
- 完全に定義された DFA を作る場合、φ からはすべての入力で φ へ遷移させる。
- 受理状態は「集合に NFA の受理状態が含まれれば」
- 最小化は任意だが、実装上の効率化のために実施することを推奨
- まず受理・非受理で初期分割し、同一遷移を持つグループを統合する（分割法）。
5. ちょっとしたコツ
- 状態数の上限は 2ⁿ（n は NFA の状態数）。ただし、遷移が直線的に連なる NFA では到達可能な DFA の状態は O(n) になることが多い。
- ε遷移がある場合の例：例えば q₀ から ε で q₁ に遷移できるとき、開始集合は
{q₀, q₁}になる。各ステップでも同様に、対象集合の遷移先を合併した後にその集合全体の ε閉包 を取る。 - 空集合 φ と死状態は同義であることを本文中で明示すると、初心者の混乱が防げる。
- べき集合 P(Q) を用いると「状態集合全体は NFA の状態集合 Q のべき集合に含まれる」という厳密な表現になるので、講義資料などで補足するとよい。
6. まとめ
- NFA は「1 つの入力で複数の道が走る」柔軟なモデル、DFA は「道が一本だけ」決定的なモデルである。
- 部分集合構成法 を用いれば、NFA の遷移表を書くだけで必ず等価な DFA を作れる。
- 変換のポイントは
- 状態集合を新しい状態として扱う
- 遷移先はすべての要素の遷移先を合併し、必要なら ε閉包を取る
- 空集合 φ を唯一の死状態として導入し、完全に定義された DFA を作る
- 受理状態は集合に NFA の受理状態が入っていれば OK
- 最小化は「受理・非受理で初期分割し、同一遷移を持つグループを統合」する手順で実施できる
- 手を動かして遷移表に書き込めば、NFA から DFA への変換が機械的にできることを実感できるはずです。ぜひ挑戦してみてください。
