非決定性有限オートマトン（NFA）を深掘りする：理論・変換・実装・応用

2025年12月16日 最終更新日時 : 2025年12月16日 エバープレイ編集部

はじめに

非決定性有限オートマトン（NFA: Nondeterministic Finite Automaton）は、計算理論と形式言語の中心的な概念です。NFAは決定性有限オートマトン（DFA）と同じ「正規言語」を記述しますが、表現力や設計のしやすさ、変換や性能特性において特徴的な振る舞いを持ちます。本稿では、NFAの定義と基本性質、ε遷移や部分集合構成（決定化）、正規表現との関係、計算複雑性、実装上の注意点や実用的応用（正規表現エンジンや字句解析）まで、詳細かつ厳密に解説します。

NFAの形式定義

NFAは五つ組 (Q, Σ, δ, q0, F) で定義されます。

  • Q: 有限の状態集合
  • Σ: 入力アルファベット（有限集合）
  • δ: 遷移関数。NFAでは δ: Q × (Σ ∪ {ε}) → P(Q)（状態集合の冪集合）として、同じ入力やε（空文字）で複数の遷移先を許します。
  • q0 ∈ Q: 初期状態
  • F ⊆ Q: 受理状態集合

受理の定義は「ある入力文字列 w ∈ Σ* に対して、初期状態から w を消費して受理状態に到達する遷移列が存在する」ことです。ここで重要なのは “存在する” という非決定性の性質で、複数の経路のうちどれか一つでも受理に至れば受理されます。

ε（イプシロン）遷移とε-閉包

ε遷移は、入力を消費せずに状態を移る遷移です。ε遷移を含むNFA（ε-NFA）は設計が簡潔になりますが、理論的にはε遷移を除去して同等な NFA を作成できます。計算上はε-閉包（epsilon-closure）が重要です。ある状態集合 S の ε-閉包は、S に含まれる状態から ε 遷移だけで到達可能な全状態の集合です。決定化やシミュレーションでは、遷移の前後に必ず ε-閉包を取る操作が現れます。

決定化（部分集合構成法）と状態爆発

NFA は DFA と同じ言語クラス（正規言語）を受理しますが、NFA を DFA に変換するために部分集合構成（powerset construction）を使います。基本手順は次の通りです。

  • DFA の状態は NFA の状態集合（Q の部分集合）を表す。
  • 初期状態は NFA の初期状態の ε-閉包。
  • ある DFA 状態 S に対し、入力 a に対する遷移は、S 中の各状態から a で到達する状態の合併を取り、さらにその ε-閉包を取った集合。
  • DFA の受理状態は、部分集合が NFA の受理状態を少なくとも1つ含むもの。

この変換で最悪ケースの状態数は 2^n （n は元の NFA の状態数）に膨張する可能性があり、これを状態爆発と呼びます。従って効率面では NFA のままシミュレートしたほうが良い場面（メモリを節約できる、実装が単純になる等）もあります。

正規表現との関係（Kleeneの定理、Thompson構成）

Kleeneの定理は、正規表現で表される言語と有限オートマトンで受理される言語が同じクラス（正規言語）であることを示します。実務では次の二つの構成が重要です。

  • 正規表現 → NFA: Thompsonの構成により、正規表現を線形サイズのε-NFAに変換できます。Thompson NFA は状態数が正規表現の長さに線形に比例し、実装が容易で正規表現エンジン（多くの実装）で使われます。
  • NFA → 正規表現: 一般的には GNFA（Generalized NFA）を用いて帰納的に変換しますが、得られる正規表現は指数的に長くなることがあるため実践では注意が必要です。

閉包性と決定可能性

正規言語は多くの演算に対して閉じています。NFA を用いて直感的に構成できる操作もあります。

  • 和（union）: 二つの NFA を新しい初期状態から ε 遷移で接続するだけで実現可能。
  • 連接（concatenation）: 第一の NFA の受理状態から第二の NFA の初期状態へ ε 遷移を張ればよい。
  • Kleene star: 初期状態と受理状態を工夫して ε 遷移を入れる構成で可能。
  • 交差（intersection）: 正規言語は交差に対して閉じていますが、NFA だけで簡単に構成する方法はなく、通常は DFA に変換して直積（product）構成を行います。
  • 補集合（complement）: NFA の補集合を得るには、まず DFA に変換してから補集合（受理状態の反転）を取る必要があります。

決定可能性の観点では、入出力文字列が与えられたときの受理判定（membership）は線形時間で可能です（NFA を直接シミュレートしても、DFA に決定化しても）。一方、NFA の同値性（L(A)=L(B) の判定）や包含性、普遍性（Σ* かどうか）などの問題は一般に PSPACE-完全であり、容易ではありません。

計算複雑性の要点

いくつかの重要な複雑度結果を整理します（正確な難易度は理論計算機科学の定理に基づく）。

  • NFAの同値性判定: PSPACE完全（決定論的多項式空間で解けるが多項式時間アルゴリズムは知られていない）
  • NFAの包含・普遍性判定: PSPACE完全
  • NFA最小化（状態数最小の等価NFAを求める問題）: NPやPSPACEに関する難しさがあり、一般に困難（正確にはPSPACE-困難／完全であるという結果が知られている文献があります）

これらは理論上の最悪ケースであり、実用上の NFA 操作や最適化にはヒューリスティクスや部分的なアルゴリズムが使われます。

NFAの実装とシミュレーション手法

実装面では主に二つのアプローチがあります。

  • 部分集合シミュレーション（DFA相当の動的構成）: 入力を逐次読み，現在の状態集合を保持して遷移を計算する方法。最悪で状態集合の数が指数的になることはあるが、平均的には効率的。Thompson NFA のシミュレーションに近い。
  • バックトラッキング（探索）: 非決定的な遷移を再帰的に試す方法。エンジン実装が単純だが，最悪ケースで指数時間になり ReDoS（正規表現の拒否サービス攻撃）の原因になりうる。多くの実装は工夫を加えて無駄な再探索を抑える。

また、正規表現エンジンの世界では「Thompson NFA による線形時間マッチング」と「バックトラッキング型エンジン（PerlやPCREなど）」の二派があり、前者は最悪ケースでも線形時間、後者は表現によっては指数時間になる点で差があります（Russ Cox による解説が有名です）。

具体例：簡単な NFA の設計

言語 L = { w ∈ {a,b}* | w は "ab" で終わる } を受理する NFA を考えます。状態 q0（初期）, q1, q2（受理）を用意し、遷移は次のように定義します。

  • q0 --a--> q1
  • q0 --b--> q0
  • q1 --a--> q1
  • q1 --b--> q2
  • q2 --a--> q1
  • q2 --b--> q0

この NFA は実は DFA 構造ですが、NFA の自由度を使えばより簡潔に ε 遷移を使った構成で設計することもできます。重要なのは受理条件が "存在する受理経路" である点です。

応用例：字句解析器と正規表現ライブラリ

実務で NFA が重要なのは、正規表現処理や字句解析（Lexical Analysis）です。コンパイラの字句解析器は通常、正規表現から DFA を構築（部分集合構成で決定化し最小化）して高速な線形時間分析を行います。一方、テキスト処理やスクリプト言語の正規表現では、実装方針により NFA ベース（Thompson）やバックトラッキングベースのエンジンが使われ、性能特性や安全性（ReDoS の脆弱性）に違いが出ます。

設計上の注意点と実務的助言

  • 正規表現を実装やセキュリティの観点で使う場合は、エンジンの特性（NFAベースかバックトラッキングか）を理解する。バックトラッキング型は複雑な正規表現で ReDoS の危険がある。
  • 大きな NFA を DFA に変換すると状態爆発でメモリ不足になるため、必要な場面だけ決定化を行うか、遅延決定化や部分決定化（必要な部分集合のみ生成）を検討する。
  • ε遷移は設計や変換を簡単にするが、シミュレーション時には ε-閉包の計算を適切に最適化すること。

まとめ

NFA は理論的に短く表現しやすく、正規表現との結びつきや設計上の直感性に優れます。一方で、決定化による状態爆発や同値性判定の計算複雑性といった理論的な制約も抱えます。実装では部分集合シミュレーションやThompson構成を用いたアルゴリズムが現実的で、用途に応じて DFA 化やバックトラッキングの採否を判断することが重要です。

参考文献

Wikipedia: 有限オートマトン（日本語）

Wikipedia: Nondeterministic finite automaton（英語）

Hopcroft, Motwani, Ullman - Introduction to Automata Theory, Languages, and Computation（教科書）

Michael Sipser - Introduction to the Theory of Computation（教科書）

Russ Cox - Regular Expression Matching Can Be Simple And Fast（正規表現エンジン解説）

カテゴリー
IT
前の記事
マイクロフォーサーズのセンサーサイズ徹底解説：性能・特性・選び方New!!
2025年12月16日
次の記事
最新ガイド：ロボット掃除機の仕組み・選び方・運用メンテナンス完全解説（2025年版）New!!
2025年12月16日