決定性有限オートマトン
決定性有限オートマトン（けっていせいゆうげんオートマトン、）または決定性有限状態機械（けっていせいゆうげんじょうたいきかい、）は、状態と入力によって次に遷移すべき状態が一意に定まる有限オートマトンである。DFA と略記される。
DFAは入力文字列を受け付ける。各入力文字について、遷移関数にしたがって新たな状態に遷移する。最後に入力文字を受け付けたとき、受理状態であれば入力文字列は受理された、そうでなければ入力文字列は拒否されたと判断される。
非決定性有限オートマトンは、決定性有限オートマトンと同じように正規集合を認識でき、必ず決定性オートマトンに変換できる。