有限オートマトン入門：DFA/NFAの仕組みと正規言語の理論と実践的応用
エバープレイ編集部有限オートマトンとは — 概念の概要
有限オートマトン（有限状態機械、finite automaton, FA）は、有限個の状態を持ち、入力文字列を逐次読み取りながら状態遷移を行い、受理・非受理を判定する数学的モデルです。計算理論では「正規言語（regular languages）」を定義する中心的な概念であり、正規表現や正規文法（タイプ3文法）と同等の表現力を持ちます。実装面では字句解析（lexer）や簡易なプロトコル検査、回路設計など幅広い応用があります。
形式的定義
典型的な有限オートマトンとして次の2種が扱われます。
- 決定性有限オートマトン（DFA: Deterministic Finite Automaton）: 5つ組 (Q, Σ, δ, q0, F)
- 非決定性有限オートマトン（NFA: Nondeterministic Finite Automaton）: 5つ組 (Q, Σ, Δ, q0, F)、およびε遷移を許すNFAϵ
ここで Q は有限な状態集合、Σ は有限な入力アルファベット、q0∈Q は初期状態、F⊆Q は受理状態集合、δ（またはΔ）は遷移関数（DFAでは各入力に対して遷移先が一意）です。NFAでは同じ入力に対して複数の遷移が許され、ε遷移は入力を消費せず状態を遷移できます。
DFA と NFA の等価性
DFA と NFA は表現力が同じで、任意の NFA に対して等価な DFA を構成できます（部分集合構成：subset construction）。ただし、NFA を DFA に変換すると状態数が最大で 2^|Q| に増える可能性があり、状態爆発の原因になります。逆に DFA は明示的な一意遷移を持つためシミュレーションは効率的です。
正規言語と閉包性
有限オートマトンで受理される言語は「正規言語」と呼ばれ、以下の性質を持ちます。
- 正規表現、DFA、NFA、正規文法は同じ言語クラスを定義する（表現力の等価性）。
- 正規言語は和（和集合）、連接、スター（Kleene star）、補集合、共通部分、差などに関して閉じています。特に補集合で閉じているため、DFA の受理状態を反転すれば補言語を得られます。
代表的なアルゴリズムと理論的事実
- 部分集合構成（NFA→DFA）：NFA の各状態集合を DFA の状態として扱うことで決定化する。最悪で指数的な状態増加を招く。
- 最小化：DFA の状態を同値類にまとめることで最小状態数の DFA を得ることができ、最小 DFA は同型を除けば一意です。Hopcroft のアルゴリズムは O(n log n)（n は状態数）で最小化できます。
- 受理問題（membership）：DFA の場合は入力長に比例して線形時間で判定でき、NFA も逐次にε-閉包を計算してシミュレートすれば多項式時間で判定可能です（部分集合構成を事前に行わなくても、逐次の集合更新で線形時間に近く処理できる実装が多い）。
- 空性判定（emptiness）：DFA/NFA いずれも、開始状態から受理状態に到達可能かを探索すれば判定でき、グラフの到達可能性問題に帰着します。
- 等価性・包含関係：2つの DFA の等価性は直積オートマトンを用いて多項式時間で判定可能です。一方、NFA の等価性・包含判定は一般に計算量が高く、PSPACE 完全であることが知られます（理論的に扱いが難しい場合があります）。
証明手法：ポンピング補題と Myhill–Nerode 定理
正規性を否定する際の代表的な道具が「ポンピング補題（pumping lemma）」です。正規言語ならば十分長い語を一定のブロックに分割し、あるブロックを任意回繰り返しても言語に残る性質があるため、これを満たさない言語（例：{a^n b^n | n≥0}）は正規でないことが示せます。
より構造的な特性を示すのが Myhill–Nerode 定理で、言語の同値関係（将来の接尾辞に対する区別可能性）に基づき最小 DFA の状態数を下界として与えます。これにより「最小 DFA の状態数が無限ならばその言語は正規でない」などの結論を得られます。
実践面での応用
- 字句解析（コンパイラの lexer）: 正規表現で定義されたトークンを効率的に認識するために NFA→DFA→最小化 の流れで実装されます（例: lex, flex）。
- 正規表現エンジン: 理論上の正規表現は有限オートマトンに対応しますが、Perl 互換の正規表現（PCRE）などはバックリファレンス等により非正規な言語を受理するため、バックトラッキングによる爆発的時間が発生することがあります。理論的な DFA ベースの実装は線形時間だが、一部の機能は実装上難しい場合があります。
- ハードウェア回路・組込み: 状態機械として直に実装できるため、プロトコル検査や簡易な入力検証に有用です。
- 形式手法・モデル検査: 状態遷移系の抽象化として有限オートマトンが用いられます（ただし、モデルの複雑さに応じて状態爆発問題がある）。
限界と注意点
有限オートマトンは「有限の記憶」しか持たないため、入出力の長さを数えるような無限の記憶が必要な言語（例: a^n b^n）は扱えません。文脈自由言語（CFG）やさらに強力な計算モデル（スタック付きオートマトン、チューリング機械）が必要になります。
また、実用的な正規表現ライブラリの振る舞い（backreference 等）や、NFA→DFA 変換による状態爆発を考慮して、実装や性能評価を行う必要があります。
具体例
簡単な例として、アルファベット {0,1} 上で 0 の個数が偶数である言語は DFA で 2 状態で実現できます（状態 q_even, q_odd）。一方、言語 {0^n1^n | n≥0} はポンピング補題により正規ではないと示せます。
まとめ
有限オートマトンは理論的には正規言語の基盤であり、実務的にも字句解析や簡易な検査に不可欠なツールです。DFA と NFA の等価性、最小化や部分集合構成といったアルゴリズム的事実、ポンピング補題や Myhill–Nerode のような証明技法を理解することで、設計や性能上の落とし穴を避けつつ応用できます。特に実装では、バックトラッキング型の正規表現と DFA ベースの実装の違い、状態爆発への対処（部分的な遅延決定やヒューリスティクス）に注意してください。
参考文献
- Finite automaton — Wikipedia
- Deterministic finite automaton — Wikipedia
- Nondeterministic finite automaton — Wikipedia
- Regular language — Wikipedia
- Pumping lemma for regular languages — Wikipedia
- Myhill–Nerode theorem — Wikipedia
- Hopcroft's algorithm — Wikipedia
- Subset construction (powerset construction) — Wikipedia
- Sipser, M. — Introduction to the Theory of Computation (lecture notes/slides)
- Regular expression implementation — Wikipedia (backtracking vs DFA)
投稿者プロフィール
