決定性有限オートマトン
DFA とは5組 A = (Q, Σ, δ, q0, F) のうち以下の性質(右側)を満たすものをいう。それぞれの要素は以下(左側)のように呼ばれる。
状態集合 (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の理解する言語である。