Deterministic Finite Automaton, DFA

現在の状態が何であれ、読む文字が何であれ、機械が次にどの状態になるかが決まっている

非決定性有限オートマトンでは、その入力が受理されるかどうかを確認するためには取れる道筋を全て試す必要があった

これでは効率が悪い

なので、非決定的な遷移を取り除いた決定性有限オートマトンを使うのが良い

非決定性有限オートマトンに以下の制約を加えている

\epsilonによる遷移がない

一つの状態から同じ記号による異なった状態への遷移はない

決定性とは以下を満たす性質のこと

矛盾がないこと

規則同士の競合がない

省略がないこと

あらゆる入力に対し、少なくとも1つの規則が当てはまる

つまり、状態と入力の組み合わせに対して、必ず1つだけ規則を持つ。

逆に言えば、1つの状態から同じ記号(下図でいうaやb)でラベリングされた2つの辺が出ることはない

↑こういうのがあるとそれは非決定性有限オートマトンになる

例

二重丸は受理状態

参考