NFA（非決定性有限オートマトン）を徹底解説：理論、構成法、実装と応用
エバープレイ編集部概要：NFAとは何か
NFA（Non-deterministic Finite Automaton、非決定性有限オートマトン）は、理論計算機科学における形式的モデルの一つで、有限の状態集合と入力シンボルに基づいて文字列を受理する抽象機械です。NFAは同等の表現力を持つDFA（決定性有限オートマトン）と比較して、状態数が少なく表現が簡潔になることが多い一方で、遷移に非決定性（複数の候補やε遷移）を許します。NFAで受理できる言語は正則言語に相当します。
形式的定義
標準的なNFAは5組 (Q, Σ, δ, q0, F) で定義されます。
- Q：有限の状態集合
- Σ：有限の入力アルファベット
- δ：遷移関数で、通常はδ: Q × (Σ ∪ {ε}) → P(Q)（P(Q)はQの部分集合）として表され、ある状態と入力記号（あるいはε）に対して遷移し得る状態集合を返す
- q0：開始状態（q0 ∈ Q）
- F：受理状態の集合（F ⊆ Q）
ポイントは遷移が集合を返す点で、ある入力位置で複数の次状態があり得る（非決定性）こと、そしてε（空文字）遷移を許すNFA-εの概念が存在することです。
ε遷移（空遷移）の役割
ε遷移は入力を消費せずに状態遷移が可能な機能です。正規表現からNFAを構築する際（Thompsonの構成など）、結合や繰り返しを表現するために頻繁に用いられます。ε遷移を含むNFAは解析や変換の際に一度ε-閉包（εで到達可能な全ての状態集合）を計算する必要がありますが、理論上はε遷移を除去して等価なNFAやDFAに変換することが可能です。
NFAとDFAの関係：等価性と決定化（subset construction）
NFAで受理される言語は必ずDFAでも受理できます。これが意味するのは、NFAとDFAは同じクラスの言語（正則言語）を表現できるということです。DFAへの変換には部分集合構成法（powerset construction）が用いられます。
- 部分集合構成の主要な考え方：DFAの各状態を、元のNFAの状態集合（部分集合）に対応させ、ε-閉包を考慮して遷移を定義する。
- 結果として生成されるDFAの状態数は理論上最大で2^{|Q|}に達する可能性があり、これは決定化の際の指数爆発の原因となる。
したがって、NFAは表現が簡潔でも、決定化すると状態数が爆発的に増える可能性がある点に注意が必要です。
NFAのアルゴリズム的扱いと計算量
主なアルゴリズム的課題は「ある文字列がNFAで受理されるか（メンバーシップ問題）」です。効率的なシミュレーション法として次の2つがよく使われます。
- 部分集合シミュレーション：入力を左から右へ走査し、現在到達可能なNFAの状態集合を保持する方式。各入力記号ごとに遷移をたどり、ε-閉包を計算する。計算量はO(n·|Q|^2)や実装次第でO(n·|Q|+|E|)に近づけられる（nは入力長、|Q|は状態数、|E|は遷移数）。
- バックトラック（深さ優先）型：非決定性の選択を再帰的に試す方法。最悪ケースで指数時間になる可能性があるため、現代の正規表現エンジンでは注意して使われる。
実際の性能は実装（ビット集合を用いる、NFAを局所最適化する、遷移構造の圧縮など）に大きく依存します。
NFAの構築法：正規表現からの自動化
正規表現→NFAの典型的技法はThompsonの構成で、各正規演算子（連接、和（|）、閉包（*））に対して小さなNFA部品を作りε遷移でつなぎます。Thompson NFAは決定化しやすく、実装も単純なので、多くの正規表現エンジンの基礎に用いられます。
逆にNFA→正規表現変換には状態消去法（state elimination）などの手法があり、有限オートマトンから等価な正規表現を構築できますが、生成される正規表現は冗長になりやすいという特徴があります。
理論的性質と閉包性
NFA（およびDFA）が受理する正則言語は以下の演算に対して閉じています：
- 和（合併）
- 連接
- クリーニー星（*）
- 補集合、交差（ただし補集合についてはDFAに決定化して考える必要がある）
これらはNFAの構成的操作（新しい開始状態にε遷移で結ぶなど）や決定化＋補集合などで証明できます。Kleeneの定理は「正規表現で表現できる言語」と「（D）FAで認識できる言語」が一致することを保証します。
応用分野：実装と最適化
NFAは理論だけでなく実務でも重要です。代表的な応用例を挙げます：
- 正規表現ライブラリ：多くの実装はNFA（あるいはNFA由来のアルゴリズム）を内部に持ち、柔軟な表現力と実装の単純さを得る。Russ Coxの論文は現代的な正規表現実装のアーキテクチャ比較で有名です。
- 字句解析（レキサー）：正規言語で字句を定義し、NFA→DFAで効率化された字句解析器（たとえばlex/flex）が用いられる。
- 検証ツールやモデル検査：状態空間表現の1つとしてNFAが使われることがある。
実装上のトレードオフとして、NFAベースのエンジンはバックトラッキングによる最悪ケースの遅延が問題になる一方で、DFAは決定的で線形時間だが構築コスト（メモリ）が高くなる点があります。実際のエンジンでは両者のハイブリッド技法やキャッシュ、部分的決定化などが使用されます。
高度な拡張と別モデル
非決定性有限オートマトンを拡張したモデルとして以下が挙げられます：
- 二方向NFA（2NFA）：入力テープ上を両方向に移動できる有限オートマトン。表現力は変わらないが計算過程が異なる。
- 交代オートマトン（AFA）：非決定性に加え存在量化と全称量化を導入することで表現の簡潔性が向上するが、受理言語は引き続き正則である。
- 確率的NFAや重み付きオートマトン：遷移に確率や重みを持たせ、自然言語処理や音声認識で利用される。
これらの拡張は用途により有用ですが、理論的性質（正則性、決定化の難易度など）はモデルごとに異なります。
実務的な設計上の留意点
- 正規表現や字句の規則を設計するときは、NFAの非決定性が引き起こす最悪ケースを意識する（猫の道パターン、catastrophic backtrackingなど）。必要ならDFA化や部分的な最適化を検討する。
- メモリ制約が厳しい場合はNFAベースの遅延評価やビットセット最適化（bitset NFAシミュレーション）を使うとよい。
- デバッグや可視化のためにNFAを描画するツールを用いると、意図しない非決定性を発見しやすくなる。
まとめ
NFAは理論的に美しく、実用的にも重要なモデルです。非決定性により表現が簡潔になる反面、決定化時に状態数が指数的に増える可能性や、実装上の時間的・空間的トレードオフが存在します。正規表現、字句解析、モデル検査など幅広い分野で利用されており、Thompsonの構成、部分集合構成、ε-閉包といった基本的手法を押さえることが、NFAを正しく扱うための鍵です。
参考文献
- Wikipedia: Nondeterministic finite automaton
- Wikipedia: Thompson's construction
- Russ Cox, "Regular Expression Matching Can Be Simple And Fast"
- Michael Sipser, "Introduction to the Theory of Computation" (参考文献としての概説)
- Wikipedia: Kleene's theorem
投稿者プロフィール
