決定性有限オートマトン(DFA)を例を用いて分かりやすく解説!

決定性有限オートマトン
この記事のまとめ

・決定性有限オートマトンは「次の状態が一意に決定する状態数が有限個のオートマトン」

・どのような入力文字列であれば、開始状態から受理状態へちょうど遷移できるかが重要

・「次の状態が一意に決定しない」のは非決定性有限オートマトン

決定性有限オートマトンとは?

決定性有限オートマトンとは一言で言えば、「次の状態が一意に決定する状態数が有限個のオートマトン」です。英語では「Deterministic Finite Automaton」と書くので、頭文字を取って「DFA」とも呼ばれます。

オートマトンが良く分からない人はとりあえず「入力によって状態が変化するもの」と覚えておいてください。

簡単な例で理解を深めましょう。

先生
先生

決定性有限オートマトンの例

例1

以下の図のオートマトンが「決定性有限オートマトン」です。

といっても習いたての人はこの図が何を表しているのかよく分からないと思うので、各パーツの意味を説明しましょう。次の表をご覧ください。

この表より、「入力文字列により開始状態から普通の状態や受理状態に遷移する」ものがオートマトンであると言えるでしょう。

で、ここで重要なのは、「どのような入力文字列であれば、開始状態から受理状態へちょうど遷移できるか?」ということです。

最初の図を見れば、入力「$a$」で➀から②へ遷移し、入力「$b$」で②から③へ遷移しているため、入力文字列が「$ab$」であれば開始状態から受理状態へとちょうど遷移することが出来ると分かりますね。

このとき、この決定性有限オートマトンは入力文字列$ab$を「受理する」と言います。

くるる
くるる

入力文字列「$aba$」も受理状態に到達するから受理されるんすか?

受理されません!

先生
先生

今回の例では③の後に遷移先がありませんが、実はそのような状態で次の入力が与えられた場合は、問答無用でその入力は不受理になるのです。

つまり、ただ受理状態に到達すれば良いのではなく、「ちょうど」受理状態にいなければならないのです。

だから、入力文字列「$a$」は当然受理されませんし、「$abab$」なんてのも受理されません。今回の例では「$ab$」という文字列だけが受理されるのです。

例2

さて、次のようなオートマトンも決定性有限オートマトンです。

状態➀の円を描いている矢印は「状態➀にいるときに$b$が入力されたら、次の状態も状態➀」ということを表しています。つまり、今の状態から動かないわけです。

さて、このオートマトンが受理する文字列は何かを考えます。「$bab$」や「$ab$」が受理されるというのは簡単に分かるでしょう。

また、最初に「$b$」がいくつか入力されて、そのあとに「$ab$」が入力されるという場合も受理されそうです。

受理される文字列の集合を1つにまとめて表現してみましょう。

先生
先生

ここで、使うのが「閉包」という概念です。閉包とは「ある文字を0回以上繰り返した文字列の集合」のことで、「$*$」という記号を使って表されます。

例えば、$b^*= \{\varepsilon, b, bb, bbb, \cdots \}$という感じです。$\varepsilon$は空文字列を表しています。

この記号を使うと、例2のオートマトンが受理する文字列は「$b^{*}ab$」と書けます。

ちなみに、このような表現の仕方を正規表現といい、他にも「または」を表す「$ \ | \ $」などが使われます。「オートマトンで受理される文字列を正規表現で答えなさい。」という問題が出た場合は、この正規表現を使って答えるのです。

決定性有限オートマトンではない例

“決定性”有限オートマトンがあるのであれば、当然”非決定性”有限オートマトンもあります。

非決定性有限オートマトンは「次の状態が一意に決定しない状態数が有限個のオートマトン」で、次のようなオートマトンのことをいいます。

このオートマトンは入力「$a$」が与えられたときに、状態②に遷移するか、状態④に遷移するかが一意に決まりませんよね?

このようなオートマトンは決定性有限オートマトンではないのです。

非決定性有限オートマトンについて詳しく知りたい方はこちらの「非決定性有限オートマトン(NFA)を分かりやすく解説!」の記事をご覧ください。

非決定性有限オートマトン

非決定性有限オートマトン(NFA)を例を用いて分かりやすく解説!

例題

以下の決定性有限オートマトンについて次の問に答えよ。

(1) 文字列「$bbabaa$」は受理されるか?

(2) 受理する文字列を正規表現で答えよ。

解答

(1) 受理される

(2) $b^*a(a|ba^*)$

この記事のまとめ

・決定性有限オートマトンは「次の状態が一意に決定する状態数が有限個のオートマトン」

・どのような入力文字列であれば、開始状態から受理状態へちょうど遷移できるかが重要

・「次の状態が一意に決定しない」のは非決定性有限オートマトン

シェアしてね!

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です