決定性有限オートマトン

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

これでは効率が悪い

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

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

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

矛盾がないこと

規則同士の競合がない

省略がないこと

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

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

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

例

https://i.stack.imgur.com/JpLX5.jpg

二重丸は受理状態

参考