※画像はイメージです。本文と直接の関係はありません

NFA から DFA への変換手順とコツ徹底解説

はじめに（結論ファースト）

非決定性有限オートマトン（NFA）は 部分集合構成法 を用いれば、必ず同一言語を認識する決定性有限オートマトン（DFA）に変換できます。本稿では変換手順を 5 ステップ に分け、具体例と実装上のポイントを解説します。これを読めば、課題やアルゴリズム設計で「NFA → DFA」変換を正確に行えるようになります。

用語集（冒頭に配置）

ε（イプシロン）遷移：入力シンボルを消費せずに状態が変わる遷移。
ε 閉包：ある状態集合から 自分自身を含み、ε 遷移だけをたどって到達できるすべての状態 の集合。
部分集合構成法：NFA の状態集合のすべての部分集合（空集合 ∅ も含む）を DFA の状態として列挙し、遷移を定義する手法。
空集合 ∅：遷移先が存在しないことを表す集合。
死状態（空集合 ∅）：DFA の遷移関数を全域関数に保つため、遷移先が無いときに遷移させる「空集合」状態。

1. NFA と DFA の基本

状態遷移：同じ入力シンボルに対して複数の遷移先が許され、遷移先が 空集合 ∅ になることもあります。
初期状態：形式上は単一の開始状態 (s_{0}) を持ちます。ε‑遷移がある場合はその ε 閉包 を計算すれば、実質的に複数開始状態を表現できます。
受理条件：入力全体を処理した後に 少なくとも 1 つ の受理状態に到達すれば文字列は受理されます。

2. 変換の全体像（部分集合構成法）

任意の NFA
[ M_{N}= (K,\Sigma,\delta_{N},s_{0},F_{N}) ]
に対して、同じ言語を認識する DFA
[ M_{D}= (2^{K},\Sigma,\delta_{D},\text{ε閉包}(s_{0}),F_{D}) ]
を構成できることが理論上保証されています。

状態集合　(2^{K}) は元の状態集合 (K) の すべての部分集合（空集合 ∅ も含む）です。
遷移関数
[ \delta_{D}(S,a)=\bigcup_{q\in S}\delta_{N}(q,a) ]
ここで (\delta_{D}) は「集合 (S) が入力シンボル (a) を受け取ったときに遷移できる全状態の集合」を表します。
受理状態集合
[ F_{D}= {\,S\subseteq K \mid S\cap F_{N}\neq\varnothing\,} ]
すなわち「元の NFA の受理状態を 少なくとも 1 つ 含む集合全体」が DFA の受理状態になります。

3. 変換手順 5 ステップ

ステップ 1　NFA の遷移表を作成する

行に状態、列に入力シンボル（例：0 と 1）を並べ、遷移先の集合を書き込みます。
初期状態は「⇒」で、受理状態は別列「受理」に「*」で示します。遷移先が無いときは空集合 ∅ と表記します。

ステップ 2　状態集合の列挙と遷移の計算

初期集合は ε 閉包((s_{0})) です。ε が無い場合は ({s_{0}}) がそのまま ε 閉包になります。
キューに初期集合を入れ、未探索の集合がなくなるまで次の処理を繰り返します。
- キューから集合 (S) を取り出す。
- 各入力シンボル (a) について
  [ T=\bigcup_{q\in S}\delta_{N}(q,a) ]
  を計算し、必要ならばその ε 閉包 も取ります。
- 得られた集合 (T) が表にまだ無ければ表に追加し、キューに入れます。
この過程で 空集合 ∅ が遷移先として現れた時点で、∅ も DFA の一状態として扱います。DFA の遷移関数は全域関数である必要があるため、どの入力でも必ず遷移先が定義されるように死状態（空集合 ∅）を用意します。

ポイント：ステップ 2 では集合を列挙しながら同時に遷移先を計算する「動的探索」になるため、全ての (2^{n}) 個を事前に書き出すという誤解を防げます。

ステップ 3　遷移図の完成と受理状態の特定

ステップ 2 で列挙したすべての状態集合について、各入力シンボルの遷移先を表に記入し、「元の NFA の受理状態を 1 つでも含むか」 を基準に受理状態かどうかを判定します。これにより 完全な遷移表 と 受理状態の一覧 が得られ、DFA の遷移図を描くことができます。

ステップ 4　到達不可能状態の除去

キュー探索により生成された集合はすべて 初期状態から到達可能 です。したがって、表に残っている状態だけが実際に使用されます。不要な状態が混入している場合はここで除去します。
- 死状態 ∅ は全域関数を満たすために必須です。到達可能であればそのまま残し、自己遷移させて DFA を完全にします。
- 到達不可能な集合があれば削除して構いませんが、実装上はキュー探索だけで生成されるため通常は現れません。

ステップ 5　最小化（オプション）

変換自体はステップ 4 で完了しますが、得られた DFA をさらに小さくしたい場合は以下の手順で最小化します。
1. 「受理状態」と「非受理状態」を別々のブロックに分けます。
2. 各入力シンボルについて、同一ブロック内の状態が遷移先として 同じブロック に属するかどうかでブロックを細分化します。
3. すべてのブロックで遷移先が同一ブロックに属し続けるまで分割を繰り返します。
4. 収束したブロックが最小 DFA の状態になります。死状態 ∅ もこの対象に含めます。

4. 具体例で見る変換の流れ

例題　「0 が 0 回以上続き、最後に 1 が出る文字列（0*1）」を受理する NFA

1. NFA の定義

状態集合　(K={q_{0},q_{1},q_{2}})
入力アルファベット　(\Sigma={0,1})
初期状態　(s_{0}=q_{0})
受理状態　(F_{N}={q_{2}})
遷移関係（ε 遷移はなし）
- (q_{0}) : 0 → ({q_{0},q_{1}}) , 1 → ∅
- (q_{1}) : 0 → ∅ , 1 → ({q_{2}})
- (q_{2}) : 0 → ∅ , 1 → ∅

2. 状態集合の列挙（ステップ 2）

初期集合は ({q_{0}})。
キュー処理の結果、到達可能な集合は次の 4 つです。
1. ({q_{0}})
2. ({q_{0},q_{1}})（0 遷移で得られる）
3. ({q_{2}})（({q_{0},q_{1}}) の 1 遷移で得られる）
4. 空集合 ∅（遷移先が無い場合に生成）

3. DFA の遷移表（ステップ 3）

・({q_{0}})：({q_{0},q_{1}}) ・({q_{0},q_{1}})：({q_{0},q_{1}}) ・({q_{2}})：∅ ・∅：∅

4. ASCII アートで示す遷移図（視認性向上）

[ {q0} ] --0--> [ {q0,q1} ] --1--> [ {q2} ]*   (受理)
   |                |                |
   1                0                0,1
   v                v                v
  [ ∅ ] <----------[ ∅ ]<-----------[ ∅ ]

矢印の上に入力シンボルを記載しています。
受理状態は * で示しています。
死状態（∅）はすべて自己遷移し、全域関数を満たします。

5. 到達不可能状態の除去（ステップ 4）

列挙されたすべての集合は初期状態から到達可能です。死状態 ∅ は自己遷移させたまま残します。

6. 最小化（ステップ 5、オプション）

受理ブロック　({{q_{2}}})
非受理ブロック　({{q_{0}},{q_{0},q_{1}},∅})

非受理ブロック内で 0 と 1 の遷移先が異なるため、これ以上の分割は生じません。したがって、最小化後も 4 つの状態が残ります。

7. 最終 DFA の概要

初期状態 ({q_{0}}) → 0 で ({q_{0},q_{1}})、1 で ∅
({q_{0},q_{1}}) → 0 で ({q_{0},q_{1}})、1 で ({q_{2}})（受理）
({q_{2}}) は受理状態で、どの入力でも ∅ に遷移
∅ は死状態で、すべて自己遷移

5. ε 遷移があるときの追加手順

各状態の ε 閉包 を計算し、元の遷移表の 0・1 の遷移先を「ε 閉包に含まれるすべての遷移先」へ置き換えます。
こうして得られた ε なし NFA を本稿の 5 ステップに投入すれば DFA が得られます。
例として、開始状態 (q_{0}) の ε 閉包が ({q_{0},q_{1},q_{2}}) になる場合、0 の遷移先はその集合の各状態が持つ 0 遷移の合併となります。

6. 実装のちょっとしたコツ（言語非依存）

死状態（∅） を必ず用意し、遷移が無いときは ∅ に遷移させることで遷移表が完全になります。
状態集合は ビット列 や ハッシュマップ で管理すると、集合演算が高速かつ言語に依存しません。
新しい集合が表に無ければ キュー で管理しながら幅優先探索で追加していくと、到達可能な集合だけを漏れなく生成できます。
switch 文や列挙型は便利ですが、利用できない言語でも「整数 ID と分岐テーブル」で同様のロジックを実装できるので、アルゴリズム自体は言語に依存しないことを意識すると良いでしょう。

7. 変換で注意すべきポイント

状態爆発
NFA が n 個の状態を持つと、理論上は最大 (2^{n}) 個の DFA 状態が生まれる可能性があります。実務では「到達可能な部分集合だけを幅優先探索で列挙」すれば必要な状態数は大幅に削減されますが、最悪ケースでは依然として (2^{n}) 個になる点は認識しておきましょう。
ε 閉包の計算漏れ
ε‑遷移がある場合は必ず ε 閉包 を正しく求め、各入力シンボルについて閉包後の遷移先集合を再計算してください。漏れると認識言語が変わってしまいます。
受理状態の判定
DFA の受理状態は「元の NFA の受理状態を 少なくとも 1 つ 含む集合全体」であることを忘れないでください。
不要状態の削除
ステップ 4 で到達不可能な集合を除去してから最小化（オプション）を行うと、分割精緻化の回数が減り計算コストが低減します。
最小化の正しい手順
受理/非受理の区分を保ち、すべての入力シンボルについて遷移先が同一ブロックに属するかでブロックを細分化し、これを収束するまで繰り返すことが必要です。遷移先が同じだけで統合すると、誤った最小化になる可能性があります。
NFA の直接利用
正規表現エンジンがバックトラッキングで NFA を直接実装するケースもあります。変換が必須ではないことを踏まえ、目的に応じて NFA と DFA のどちらを使うか選択してください。

まとめ

NFA は設計が直感的ですが、プログラム化や解析には DFA が扱いやすいです。
部分集合構成法 を用いれば、NFA の各状態集合を新しい DFA の状態として列挙すれば、必ず同一言語の DFA が構成できます。
変換は 5 ステップ（遷移表作成 → 状態集合の列挙と遷移計算 → 遷移図の完成と受理状態の特定 → 死状態追加と到達不可能状態除去 → 最小化（オプション））で体系的に進められますが、実装上はステップ 2 と 3 を同時に行う探索ループが一般的です。
ε 遷移がある場合は ε 閉包 を先に計算し、すべてのシンボルについて閉包後の遷移先集合を再計算すれば問題なく変換できます。
実装時は 死状態（∅）、ビット列やハッシュマップでの集合管理、キューによる幅優先探索 を活用するとコードがシンプルかつ高速になります。

以上の手順とポイントを押さえておけば、課題の「NFA → DFA」変換はもちろん、正規表現からのオートマトン構築や字句解析器の設計でもスムーズに対応できるでしょう。

雑記

2026/07/07