オートマトンとは何か？分かりやすく解説します！

オートマトンとは？

オートマトンってたまに聞く言葉だけど、どういう意味なんだろう？

お答えしましょう！

先生

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

例えば、「リモコンのスイッチを押して、テレビを付ける」という動作は次のような図で表すことができます。二重丸はゴールを表していて、今回の例ではテレビが付いたらゴールってことですね。

これがオートマトンです。簡単ですね。

他の例も見てましょう。例えば、「じゃんけん」ならば、相手がチョキを出している場合、次のようなオートマトンが書けますね

こんなふうに、入力によって、ある状態からある状態に遷移するのがオートマトンなのです。

抽象度を上げてみる

それでは、少し抽象度を上げてみましょう。例えば、次のようなオートマトンを考えます。

このオートマトンは「状態1のときに、$a$が入力されると、状態2に遷移する」オートマトンです。

状態1の左に見慣れない矢印が追加されていますが、初期状態がどれか一目で分かるようにするための矢印です。今までの例ではわざと書いていませんでした。

更に発展して次のようなオートマトンを考えましょう。

状態1の上に丸い矢印が書いてありますが、これは「状態1のときに、$b$が入力されると、状態1に遷移する」という意味があります。つまり自分に戻ってくるわけです。

このオートマトンにおいて、ゴール(実は受理状態っていいます）である状態2に到達するにはどのような入力が必要でしょうか？

先生

くるる

$b$が何回か入力された後に、$a$が入力されれば良さそうっす！

その通り！

先生

正確にいうと、「$b$が0回以上入力された後に、$a$が入力される」になります。ただ、わざわざ言葉で説明するのは面倒ですよね？

そのため、「0回以上」という意味の「$*$」という記号を使って、$b^{*}a$と書きます。

もっと複雑になると、次のようなオートマトンを考えたりします。

ちなみに、このオートマトンがゴール（受理状態）に到達するのに必要な入力は「$c|b^{*}a(a|bc^{*})$」です。

オートマトンの種類

オートマトンには色々な種類があります。

などなど…

少しだけ解説します。

決定性有限オートマトン

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

詳しく知りたい方は「決定性有限オートマトン(DFA)を例を用いて分かりやすく解説！」をご覧ください。

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

非決定性有限オートマトンは「次の状態が一意に決定しない状態数が有限個のオートマトン」です。つまり、決定性有限オートマトンの逆ですね。

例えば、次のオートマトンは状態1のときに、$a$が入力されると、状態2に行くのか、状態4に行くのかが分からないため、非決定性有限オートマトンです。

詳しく知りたい方は「非決定性有限オートマトン(NFA)を例を用いて分かりやすく解説！」をご覧ください。

プッシュダウンオートマトン

プッシュダウンオートマトン(PushDown Automaton : PDA)とは「スタックを持った非決定性有限オートマトン」です。

スタックとは簡単に言えば「データを後入れ先出しする構造」で、図のようなものです。

こういう構造を非決定性有限オートマトンに組み込んだのが、プッシュダウンオートマトンです。

詳しく知りたい方は「プッシュダウンオートマトン(PDA)を図を使って分かりやすく解説！」をご覧ください。

まとめ

今回はオートマトンについて簡単に解説しました。オートマトンの概念は情報系の学生ならば絶対に理解しておかなければならないものなので、しっかりと勉強しましょう！

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

2023.11.07