今回は、テキストだけではわからない!という人のために、有限オートマトンについて解法をお伝えします!
有限オートマトンとは
状態の遷移をともなう動作をモデル化して表すのをオートマトンといいます。
そのうち、有限オートマトンとは最も単純で代表的なものなのです。
状態や遷移の数が有限個で表されるモデルが有限オートマトンです。

この図では○が状態、線が遷移を表しています。これらが有限個あるということです。
このような図のことを状態遷移図と呼びます。
有限オートマトンには受理と不受理があります。
また、受理は一般的に◎で表されます。
さて、本試験ではどのような問題が出題されるのでしょうか?
問題
表は、入力記号の集合が{0,1}、状態集合が{a,b,c,d}である有限オートマトンの状態遷移表である。長さ3ビット以上の任意のビット列を左(上位ビット列)から順に読み込んで最後が110で終わっているものを受理するには、どの状態を受理状態とすればよいか。
ア a イ b ウ c エ d
(平成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を入力してみます。
順番に1⇒1⇒0を入力します。
もし 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 でおわり、正解はウとなります。
いかがでしたか?意外に簡単でしたね。
次回の記事では少し違った有限オートマトンの問題を取り上げます。
0 件のコメント:
コメントを投稿