| ブログ ログイン | トップ プロフ フレンド サークル |
|
「考える」ってったって、オートマトンの考え方は難しくない。 ある状態ものに対して、ある値を与えたら、どういう状態に遷移するかっていうことだけだ。要するにそういうこと。 問題なんていうモノは簡単に理解してしまった方がいい。 例えば、電気は「スイッチが入っていない（消灯状態）」のものに、「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」が与えられるとｃに遷移して、「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) >> |
ブログ気持玉 44
