有限オートマトン

平成28年秋季　問4．　有限オートマトン

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

Wikipediaによると、有限オートマトン（finite automaton: FA）または有限状態機械（finite state machine: FSM)とは、有限個の状態と遷移と動作の組み合わせからなる数学的に抽象化された「ふるまいのモデル」である。デジタル回路やプログラムの設計で使われることがあり、ある一連の状態をとったときどのように論理が流れるかを調べることができる。有限個の「状態」のうち1つの状態をとる。ある時点では1つの状態しかとらず、それをその時点の「現在状態」と呼ぶ。何らかのイベントや条件によってある状態から別の状態へと移行し、それを「遷移」と呼ぶ。それぞれの現在状態から遷移しうる状態と、繊維のきっかけとなる条件を列挙することで定義される。


・・・・まあ、わからんくはないがもう少しわかりやすく解説できないものか？

「ふるまいのモデル」というのはかなり端的に特徴をとらえているように思える。
以前友人と「見えずの刃」というゲームを作成していた時に、以下のような図がプログラムを書く際に「今、自分が書いているコードがどの位置にあるか」を確認するのに非常に有益だというようなことを説明してくれた。

問題文のように全てが記号だとわかりにくいが、つまりある状態にあるときに受け取る内容が次の状態への行き先を決めることだということらしい。

では、わかりやすいように「0：いいえ」「1：はい」と置き換えて状態をあてはめてはどうだろう？

名付けて「一歩先に踏み出せない喪男」の有限オートマトンっ( ﾟДﾟ)

まず「a．嫁さんを探す。相手に彼氏はいないか？」で、「いる：いいえ」で次の相手を探す。つまり「a．」に戻る。「いない：はい」で状態は「b．声をかけて反応があるか？」となる。

状態「b．」で「ある：はい」であれば状態は「d．」に移行し、「ない：いいえ」なら状態は「c．」に移行する。

状態「d．」では食事に誘い、「はい：断られる」であれば誘い続ける、つまり状態「d．」を試行し続ける。対して「いいえ：断れない」であれば状態「c．」に移行する。

状態「c．」では一歩先に進み、付き合ってと言ってみる。「b．」で反応がない場合もダメもとで付き合ってくれ、と、この男は言ってみるようだ。
「断られない：はい」で状態「b．」に戻り、再度声をかけてみる。「断られる：いいえ」で次の相手を探すことになる。

状態「d．」では断られ続けるにも関わらず食事に誘い続けるのに、状態「c．」で諦めが早すぎるのは謎だ。
それと、状態「c．」で断られないのに状態「b．」に戻ってしまうのも喪男であるが所以なのかもしれないが謎である。

さて、ここで問題に戻ると、「110」で終わる状態は何か？ということになる。
上の例で考えてみよう。

状態遷移表？を見ると最後が0で終わるのは状態「a．」と「c．」のみである。そこでそれぞれについて、逆引きで考えてみる。

状態「a．」より逆引き：
状態「c．」から断られたから「a．」に来ている。しかし、状態「c．」が「1：はい」を受け取れる口はない。ので、状態「a．」が「110」で受け入れ状態になることは不可能そうだ。

状態「c．」より逆引き：
状態「b．」からでも「d．」でも「0」を受け取って「c．」に来ることは可能だ。
状態「b．」は、「a．」から「1」を受け取ることは可能だが、「a．」は「1」を受け取ることはない、つまり断られなかったら、他の女性を探す気にはならないそうだ。いいぞっ( ﾟДﾟ)　その調子だ。

状態「d．」は、何回でも女性を食事に誘い、連れ出すまであきらめないつまり「1」を受け取れるし、状態「b．」で声をかけて反応があっても「1」を受け取れる。

つまり、「b．」⇒「d．」⇒「c．」、「d．」⇒「d．」⇒「c．」でも状態「c．」には行ける。この行動を続ければ断らない女性ならなんでも行ける彼であればすぐに嫁さんをもらえそうだが、なぜだか断らないからと言って次のステップ、例えば「手をつないでみる」とか「キスを迫ってみる」などの行動が起こせない彼は、行動が有限であるがためにこのループからは永遠に抜け出せない。。。

ちなみに喪男とは、毒男と区別して使われている用語のようだ。
毒男：　女性との接触を断つことにより高度に精神的変化を遂げた求道者
喪男：　喪男とは毒男の見習いのようなもので、学生、年齢の若い者、ポジティブな思考が残っているものはこちらに分類される。
（出典：　アンサイクロペディア「毒男」より）

毒男を有限オートマトンで表現するとこのようなところか・・・

興味があろうがなかろうが、同じところに戻るところにネガティブさがうかがえる・・・

しかしこのモデルが完成された美しささえ醸し出しているように思えるのは俺の感覚がおかしくなっているからだろうか・・・

ということを時間をかけて考えていて悲しくなってしまった　orz