決定性有限オートマトン
非輪状決定性有限オートマトン(ひりんじょうけっていせいゆうげんオートマトン、英: Acyclic Deterministic Finite Automaton)は輪状(環状)の遷移の連鎖がない決定性有限オートマトンである。ADFA と略記される。換言すれば、このオートマトンでは有限の文字列集合しか表現できない。これは非常に高速な検索が可能な単語格納データ構造として使用される。最小化したADFAは非常にコンパクトになり、そのサイズは格納されるキーの数には比例しない。実際、ある閾値を越えると、格納する単語を増やしたときにデータ構造のサイズは減少しはじめる。その閾値サイズは格納される文字列がどれだけ複雑であるかに依存する。トライ木は一種のADFAである。
決定性有限オートマトン(けっていせいゆうげんオートマトン、英: Deterministic Finite Automaton)または決定性有限状態機械(けっていせいゆうげんじょうたいきかい、英: Deterministic Finite State Machine)は、状態と入力によって次に遷移すべき状態が一意に定まる有限オートマトンである。DFA と略記される。
DFAは入力文字列を受け付ける。各入力文字について、遷移関数にしたがって新たな状態に遷移する。最後に入力文字を受け付けたとき、受理状態であれば入力文字列は受理された、そうでなければ入力文字列は拒否されたと判断される。
非決定性有限オートマトンは、決定性有限オートマトンと同じように正規集合を認識でき、必ず決定性オートマトンに変換できる。