「考える」ってったって、オートマトンの考え方は難しくない。 ある状態ものに対して、ある値を与えたら、どういう状態に遷移するかっていうことだけだ。要するにそういうこと。 問題なんていうモノは簡単に理解してしまった方がいい。 例えば、電気は「スイッチが入っていない(消灯状態)」のものに、「1」(電源ON)の値を与えてやると、 「点灯状態」に推移する。 「消灯状態」に「0」(電源OFF)の値を与えても、消灯のまま。 「点灯状態」で「1」(電源ON)を与えても、点灯のまま。 「点灯状態」で「0」(電源OFF)を与えると、消灯状態に遷移する。 つまりこういうことだ。 この図を「状態遷移図」という。 さて、これを踏まえて問いに挑む。 <平成17年春・問7> 次の表は、入力記号の集合が{0,1}、状態集合が{a,b,c,d}である有限オートマトンの状態遷移表である。 長さ3以上の任意のビット列を左から(上位ビットから)順に読み込んで最後が110で終わっているものを受理するには、どの状態を受理状態とすればよいか。 <考えてみる> 問いの表を見ると、状態aのときに「0」が与えられるとaに遷移する。「1」が与えられるとbに遷移する。 bのときに「0」が与えられるとcに遷移して、「1」が与えられるとdに遷移する。 ・・・ コレに基づいて、状態遷移図を書いてみる。 「受理」とは、遷移によって処理が正常に終了した状態をいう。 ・・・んだけど、それを考えるとこの問題は「?」になってしまう。 どれが「正常終了」なんだ?と。 最後が110なんだから、a,b,c,dの各状態で、「1,1,0」の値を与えたときに、どの状態で終了するか、を考えればいい。 そこが「受理状態」なのだ。 aのとき→「1」を与えると、bになる。bに「1」を与えるとdになる。dに「0」を与えるとcになる。 つまり、aのときに「1,1,0」を与えると、cが受理の状態ということになる。 同様に、 bのとき→「1」d、「1」d→「0」c cのとき→「1」b、「1」d→「0」c dのとき→「1」d、「1」d→「0」c すなわち、cを受理状態とすれば、いずれの状態でも受理される。 【答え】 c |
<< 前記事(2008/08/10) | ブログのトップへ | 後記事(2008/08/10) >> |
タイトル (本文) | ブログ名/日時 |
---|
内 容 | ニックネーム/日時 |
---|---|
最初はわかった(^O^) |
みっふぃー☆ 2008/08/11 07:54 |
<< 前記事(2008/08/10) | ブログのトップへ | 後記事(2008/08/10) >> |