AP | 有限オートマトン①

基本情報技術者試験・応用情報技術者試験まで残すところ約１カ月となりましたね。

今回は、テキストだけではわからない！という人のために、有限オートマトンについて解法をお伝えします！

有限オートマトンとは

状態の遷移をともなう動作をモデル化して表すのをオートマトンといいます。

そのうち、有限オートマトンとは最も単純で代表的なものなのです。

状態や遷移の数が有限個で表されるモデルが有限オートマトンです。



この図では○が状態、線が遷移を表しています。これらが有限個あるということです。

このような図のことを状態遷移図と呼びます。

有限オートマトンには受理と不受理があります。

また、受理は一般的に◎で表されます。

さて、本試験ではどのような問題が出題されるのでしょうか？

問題

表は、入力記号の集合が{0,1}、状態集合が{a,b,c,d}である有限オートマトンの状態遷移表である。長さ３ビット以上の任意のビット列を左(上位ビット列)から順に読み込んで最後が110で終わっているものを受理するには、どの状態を受理状態とすればよいか。

ア　a　　イ　b　　ウ　c　　エ　ｄ

(平成26年度春期試験)

解法

まず、a,b,c,d の4つの○を書きましょう



この表を「a [一番左列の英字] から出発するとき、0 ［一番上の行の0] が入力されれば a [0列とa行が交わるセルの英字] に行き、1 [一番上の行の1] が入力されれば b [1列とa行が交わる英字] に行く」と読んでみましょう。

そうすると、下の図のようになります。



0の時はaに行く(aに留まる)ということなので丸い矢印を描きます。

続いてbの場合に移ります。

「b [一番左列の英字] から出発するとき、0 ［一番上の行の0] が入力されれば c [0列とb行が交わるセルの英字] に行き、1 [一番上の行の1] が入力されれば d [1列とb行が交わる英字] に行く」ので下の図のようになります。



次に c 行です。

「c [一番左列の英字] から出発するとき、0 ［一番上の行の0] が入力されれば a [0列とc行が交わるセルの英字] に行き、1 [一番上の行の1] が入力されれば b [1列とc行が交わる英字] に行く」ので下の図のようになります



さいごに、d の場合です。

「d [一番左列の英字] から出発するとき、0 ［一番上の行の0] が入力されれば c [0列とd行が交わるセルの英字] に行き、1 [一番上の行の1] が入力されれば d [1列とd行が交わる英字] に行く」ので下の図のようになります



1が入力される場合は、d に留まります。

これで状態遷移図が出来上がりました。

さいごに、問題の110を入力してみます。

順番に１⇒１⇒０を入力します。

もし a から始まる場合は、a ⇒ (1) ⇒ b ⇒ (1) ⇒ d ⇒ (0) ⇒ c と遷移し、最後は c で受理されます。

もし b から始まる場合は、b ⇒ (1) ⇒ d ⇒ (1) ⇒ d ⇒ (0) ⇒ c と遷移し、最後は c で受理されます。

もし c から始まる場合は、c ⇒ (1) ⇒ b ⇒ (1) ⇒ d ⇒ (0) ⇒ c と遷移し、最後は c で受理されます。

もし d から始まる場合は、c ⇒ (1) ⇒ d ⇒ (1) ⇒ d ⇒ (0) ⇒ c と遷移し、最後は c で受理されます。

結局、すべて最後が c でおわり、正解はウとなります。

いかがでしたか？意外に簡単でしたね。

次回の記事では少し違った有限オートマトンの問題を取り上げます。