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

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

決定性有限オートマトンとは一言で言えば、「次の状態が一意に決定する状態数が有限個のオートマトン」です。

英語では「Deterministic Finite Automaton」と書くので、頭文字を取って「DFA」とも呼ばれます。

また、オートマトンとは簡単に言えば「外部からの入力によって起こる状態の変化を図で表したもの」です。

詳しく知りたい方は「オートマトンとは何か？分かりやすく解説します！」をご覧ください。

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

先生

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

例１

「決定性有限オートマトン」は以下のようなものです。

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

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

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

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

くるる

そしたら「$aba$」が入力文字列の場合も受理状態に到達するから$aba$は受理されるってことっすか？

実は受理されないのです！

先生

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

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

だから、入力文字列「$a$」は当然受理されませんし、「$abab$」なんてのも受理されません。

今回の例では「$ab$」という文字列だけが受理されるのです。

例２

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

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

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

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

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

先生

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

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

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

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

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

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

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

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

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

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

例題

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

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

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

この記事のまとめ

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

2023.11.07