決定性有限オートマトン

決定性有限オートマトン（DFA）とは

決定性有限オートマトン（Deterministic Finite Automaton, DFA）は、コンピュータ科学における重要な概念の一つで、状態と入力によって次に遷移する状態が一意に決まる有限オートマトンです。DFAは、文字列が特定のパターンに合致するかどうかを判定するために使用され、プログラミング言語の字句解析やテキスト検索など、様々な分野で応用されています。

DFAの基本的な仕組み

DFAは、以下の要素で構成されます。

状態の集合 (Q): 有限個の状態の集まり。
入力アルファベット (Σ): 入力として受け付ける文字の集合。
遷移関数 (δ): 現在の状態と入力文字に基づいて、次の状態を決定する関数。
開始状態 (q0): DFAが最初にいる状態。
受理状態の集合 (F): DFAが文字列を受理する際に到達する状態の集合。

DFAは、与えられた入力文字列を先頭から1文字ずつ読み込み、現在の状態と入力文字に応じて、遷移関数に従って次の状態へと遷移します。すべての入力文字を読み終えた時点で、DFAが受理状態にあれば、その入力文字列はDFAによって受理されたと判定されます。そうでなければ、入力文字列は拒否されます。

DFAの形式的な定義

DFAは、5つ組 A = (Q, Σ, δ, q0, F) で定義されます。それぞれの要素は以下の通りです。

Q: 有限な状態の集合
Σ: 有限な入力アルファベット
δ: 遷移関数 Q × Σ → Q
q0: 開始状態 (q0 ∈ Q)
F: 受理状態の集合 (F ⊆ Q)

ある文字列 a = a0a1 ... an-1 が与えられたとき、DFAは以下のように状態を遷移します。


qi+1 := δ(qi, ai)


もし、最終的な状態 qn が受理状態 F に含まれる場合、DFAは文字列 a を受理すると言います。

DFAの例

例えば、以下のようなDFAを考えます。

Q = {q0, q1}
Σ = {0, 1}
F = {q0}
遷移関数 δ は以下の表で定義される


このDFAは、入力文字列に含まれる0の個数が偶数である場合にのみ、その文字列を受理します。状態q0は、これまでの入力で0が偶数個出現した場合に対応し、状態q1は0が奇数個出現した場合に対応します。

このDFAの状態遷移図は以下の通りです。


(q0) 0> (q1)
| ^ |
1 | 1
v | v
(q0) <-0-- (q1)


このDFAが認識する言語は、正規表現 `1(0101)` で表される正規言語です。

非決定性有限オートマトンとの関係

非決定性有限オートマトン（NFA）は、ある状態から複数の状態に遷移できる可能性を持つオートマトンです。NFAはDFAよりも柔軟な表現が可能ですが、DFAと同様に正規集合を認識することができます。また、任意のNFAは必ず等価なDFAに変換できることが知られています。

非輪状決定性有限オートマトン（ADFA）

非輪状決定性有限オートマトン（Acyclic Deterministic Finite Automaton, ADFA）は、状態遷移にループ（輪状）が存在しないDFAです。ADFAは、有限の文字列集合のみを表現でき、非常に高速な検索が可能なデータ構造として利用されます。特に、最小化したADFAは非常にコンパクトになり、格納する単語数が増えてもサイズが増加しにくい特性があります。トライ木はADFAの一種として知られています。

まとめ

決定性有限オートマトン（DFA）は、コンピュータ科学の基礎となる重要な概念であり、様々な応用分野で利用されています。DFAは、状態遷移が一意に決まるため、効率的な文字列処理が可能であり、正規言語を認識する強力なツールとなります。また、非輪状DFA（ADFA）は、高速なデータ検索構造として、その重要性を増しています。

もう一度検索