決定性有限オートマトン
決定性有限オートマトン（けっていせいゆうげんオートマトン、英: Deterministic Finite Automaton）または決定性有限状態機械（けっていせいゆうげんじょうたいきかい、英: Deterministic Finite State Machine）は、状態と入力によって次に遷移すべき状態が一意に定まる有限オートマトンである。DFA と略記される。
DFAは入力文字列を受け付ける。各入力文字について、遷移関数にしたがって新たな状態に遷移する。最後に入力文字を受け付けたとき、受理状態であれば入力文字列は受理された、そうでなければ入力文字列は拒否されたと判断される。
非決定性有限オートマトンは、決定性有限オートマトンと同じように正規集合を認識でき、必ず決定性オートマトンに変換できる[1]。
形式的定義
[編集]DFA とは5組 A = (Q, Σ, δ, q0, F) のうち以下の性質（右側）を満たすものをいう。それぞれの要素は以下（左側）のように呼ばれる[2]。
- 状態集合 (Q : 有限集合)
- 文字集合 (Σ : 有限集合)
- 遷移関数 (δ : Q × Σ → Q)
- 開始状態 (q0 ∈ Q)
- 受理状態の集合 (F ⊆ Q)
いま a = a0a1 ... an−1 という文字集合 Σ に含まれる文字から構成される文字列が与えられたとする。各 i = 0, …, n−1 について帰納的に
- qi+1 := δ(qi, ai)
とおく。 qn ∈ F が成り立つとき、 A は文字列 a を受理すると言う。状態の列 qi は文字列 a が与えられたとき、遷移関数 δ にしたがってこのマシンが状態遷移を繰り返すことを示している。言語の中でこのマシンが受容する文字列の集合が、このDFAの理解する言語である。
例
[編集]以下は DFA である A の例であり、入力文字としては 0 と 1 を受け付けて、0の個数が偶数である入力文字列のみを受理する。
A = (Q, Σ, δ, q0, F) であるとき
- Q = {q0, q1},
- Σ = {0, 1},
- F = {q0},
- δ は以下の状態遷移表で定義される。
| 0 | 1 | |
|---|---|---|
| q0 | q1 | q0 |
| q1 | q0 | q1 |
A の状態遷移図は以下の通りである。
A の状態遷移図
状態 q0 にあるとき、それまでの入力文字列に偶数個の 0 が含まれていたことを意味し、状態 q1 にあるときは奇数個であることを意味する。1 が入力されたとき、このオートマトンの状態は変化しない。入力が終了したときの状態を見れば、入力文字列に偶数個の 0 が含まれていたか否かがわかる。
非輪状決定性有限オートマトン
[編集]非輪状決定性有限オートマトン（ひりんじょうけっていせいゆうげんオートマトン、英: Acyclic Deterministic Finite Automaton）は輪状（環状）の遷移の連鎖がない決定性有限オートマトンである。ADFA と略記される。換言すれば、このオートマトンでは有限の文字列集合しか表現できない。これは非常に高速な検索が可能な単語格納データ構造として使用される。最小化したADFAは非常にコンパクトになり、そのサイズは格納されるキーの数には比例しない。実際、ある閾値を越えると、格納する単語を増やしたときにデータ構造のサイズは減少しはじめる。その閾値サイズは格納される文字列がどれだけ複雑であるかに依存する。トライ木は一種のADFAである。
脚注
[編集]- ^ コンパイラI 原理・技法・ツール、A.V.エイホ・R.セシィ、J.D.ウルマン 共著、原田賢一 訳、サイエンス社、134頁
- ^ Hopcroft et al. 2001, p. 46.
参考文献
[編集]- Hopcroft, John E; Ullman, Jeffrey D.; Motwani, Rajeev (2001) (PDF). Introduction to automata theory, languages, and computation (2nd ed.). Addison-Wesley. ISBN 0-201-44124-1