応用情報技術者試験の過去問題。「有限オートマトン」

応用情報処理技術者試験の午前の問題に、「有限オートマトン」をテーマにした問題がちょくちょく出るようです。

用語の意味など良く分からず解けなかったので調べておきます。

以下のような問題。2017年秋期より。

まず図の状態遷移表の読み方。

左側のa,b,c,dというのが状態で、上の0,1が入力値とあります。

これは例えば、「a」という状態に「0」が入力されたら、結果が「a」となり、「1」が入力されたら「b」となる。というような意味です。

オートマトンと言われるとよく分かりませんが、ソフトウェアの設計などで用いる状態遷移表と読み方は同じです。

そして問の「どの状態を受理状態とすれば良いか」という意味。

「受理状態」は「処理の結果」というような意味です。

例えば「a」という状態に対して「110」を順に入力していくと

a（1を入力）→b（1を入力）→d（0を入力）→cとなり、受理状態はcとなります。

初期状態をb、ｃ、ｄに置き換えて考えると、110を入力すると最終的に全て「c」になる事がわかり、答えは「c」という事になります。

分かってしまえば簡単でした。

今回は以上です。

平成28-29年度 応用情報技術者 試験によくでる問題集【午後】 (情報処理技術者試験)