決定性有限オートマトン (original) (raw)

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