決定性有限オートマトン
決定性有限オートマトン（けっていせい-、Deterministic Finite Automaton）または決定性有限状態機械（けっていせいゆうげんじょうたいきかい、Deterministic Finite State Machine）は、状態と入力によって次に遷移すべき状態が一意に定まる有限オートマトンである。DFA と略記される。
DFAは入力文字列を受け付ける。各入力文字について、遷移関数にしたがって新たな状態に遷移する。最後に入力文字を受け付けたとき、受容状態であれば入力文字列は受容されたと判断され、受容状態でなければ入力文字列は拒否されたと判断される。
形式的定義
DFA は (S, Σ, T, s, A) の5要素から構成され、以下の性質を持つ。
- 状態の有限集合 (S)
- 文字の有限集合 (Σ)
- 遷移関数 (T : S × Σ → S)
- 開始状態 (s ∈ S)
- 受容状態の集合 (A ⊆ S)
ここで M は、M = (S, Σ, T, s, A) という DFA であり、X = x0x1 ... xn-1 は Σ に含まれる文字から構成される文字列とする。S の中の状態の列 r0,r1, ..., rn で以下の条件が成り立つとき M は文字列 X を受容すると言える。
- r0 = s
- i = 0, ..., n-1 の各 i について ri+1 = T(ri, xi)
- rn ∈ A.
この最初の条件で示されているのは、マシンが開始状態 s で開始することである。第二の条件では、文字列 X が与えられたとき、遷移関数 T にしたがってこのマシンが状態遷移を繰り返すことを示している。最後の条件は、Xの最後の文字を受け取った際の遷移によってマシンが受容状態になることを示している。そうでない場合、マシンはこの文字列を拒絶したと見なされる。言語の中でこのマシンが受容する文字列の集合が、このDFAの理解する言語である。
例
以下は DFA である M の例であり、入力文字としては 0 と 1 を受け付けて、0の個数が偶数である入力文字列のみを受容する。
M = (S, Σ, T, s, A) であるとき
- Σ = {0, 1},
- S = {q0, q1},
- s = q0,
- A = {q0},
- T は以下の状態遷移表で定義される。
| q0 | q1 | q0 |
| q1 | q0 | q1 |
M の状態遷移図は以下の通りである。
状態 q0 にあるとき、それまでの入力文字列に偶数個の 0 が含まれていたことを意味し、状態 q1 にあるときは奇数個であることを意味する。1 が入力されたとき、このオートマトンの状態は変化しない。入力が終了したときの状態を見れば、入力文字列に偶数個の 0 が含まれていたか否かがわかる。
非輪状決定性有限オートマトン
非輪状決定性有限オートマトン（ひりんじょうけっていせいゆうげん-、Acyclic Deterministic Finite Automaton）は輪状（環状）の遷移の連鎖がない決定性有限オートマトンである。ADFA と略記される。換言すれば、このオートマトンでは有限の文字列集合しか表現できない。これは非常に高速な検索が可能な単語格納データ構造として使用される。最小化したADFAは非常にコンパクトになり、そのサイズは格納されるキーの数には比例しない。実際、ある閾値を越えると、格納する単語を増やしたときにデータ構造のサイズは減少しはじめる。その閾値サイズは格納される文字列がどれだけ複雑であるかに依存する。トライ木は一種のADFAである。