決定性オートマトン

コンピュータ科学において、決定性オートマトンとは、ある状態から別の状態への遷移の結果が入力によって決定されるオートマトン理論の概念である。 ^{[ 1 ]： 41}

一般的な決定性オートマトンとして、決定性有限オートマトン（DFA）があります。DFAは有限状態機械であり、状態と入力記号の各ペアに対して、次の状態への遷移がただ1つだけ存在します。DFAは正規言語の集合のみを認識し、他の言語は認識しません。^{[ 1 ] : 52}

非決定性有限オートマトンから決定性有限オートマトンを構築する標準的な方法は、冪集合構成法である。^{[ 1 ]： 44}