【基本情報技術者試験】オートマトン

本記事では基本情報技術者試験で出題されるオートマトンについて書いてあります。
目次は以下の通りです。

オートマトンとは？

オートマトンは、現在の状態と入力に依存して次の状態が決まるモデル化したものです。
例えばアクセルを踏むという入力を押すと、速度があがる状態になるというイメージでいいと思います。もちろん、車の場合は入力がブレーキやハンドル、ウィンカーなどあるので、複雑になりますけど…

状態遷移図と状態遷移表

なので、簡単な例を用いてより詳細にみていきます。

上の図のことを状態遷移図といいます。
丸の中が状態で、矢印の数字が入力/出力です。基本パソコンは入力が0,1なのでこうなります。ちなみに図ではなく、表にして書くこともあります。これを状態遷移表といいます。図の例だと下の表のようになります。bS₁などは遷移元(元の状態)を示しており、aS₁などは遷移先(後の状態)を示しています。

有限オートマトンと例題

今回は以下の入力例を考えます。
「011110」
このように入力が有限であるオートマトンを有限オートマトンといいます。ではこの入力例をもとに出力値を考えましょう。初期状態をS₁と考えると、S₁に0を入力するとS₂の状態になり、出力が0となります。この作業を入力の個数分だけ行います。
S₂に1を入力するとS₄の状態になり、出力が0となります。
S₄に1を入力するとS₁の状態になり、出力が1となります。
S₁に1を入力するとS₃の状態になり、出力が1となります。
S₃に1を入力するとS₄の状態になり、出力が0となります。
S₄に0を入力するとS₄の状態になり、出力が0となります。
よって、出力は「001100」となります。

まとめ

本記事のポイントを以下にまとめます。