今日もなんだかいい天気♪

アクセスカウンタ

zoom RSS ソフトウェア開発技術者試験対策(1) -オートマトンを考える-

<<   作成日時 : 2008/08/10 19:34   >>

なるほど(納得、参考になった、ヘー) ブログ気持玉 35 / トラックバック 0 / コメント 1

「考える」ってったって、オートマトンの考え方は難しくない。
ある状態ものに対して、ある値を与えたら、どういう状態に遷移するかっていうことだけだ。要するにそういうこと。
問題なんていうモノは簡単に理解してしまった方がいい。

例えば、電気は「スイッチが入っていない(消灯状態)」のものに、「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

テーマ

関連テーマ 一覧


月別リンク

ブログ気持玉

クリックして気持ちを伝えよう!
ログインしてクリックすれば、自分のブログへのリンクが付きます。
→ログインへ
気持玉数 : 35
なるほど(納得、参考になった、ヘー) なるほど(納得、参考になった、ヘー) なるほど(納得、参考になった、ヘー) なるほど(納得、参考になった、ヘー) なるほど(納得、参考になった、ヘー) なるほど(納得、参考になった、ヘー) なるほど(納得、参考になった、ヘー) なるほど(納得、参考になった、ヘー) なるほど(納得、参考になった、ヘー) なるほど(納得、参考になった、ヘー) なるほど(納得、参考になった、ヘー) なるほど(納得、参考になった、ヘー) なるほど(納得、参考になった、ヘー) なるほど(納得、参考になった、ヘー) なるほど(納得、参考になった、ヘー) なるほど(納得、参考になった、ヘー) なるほど(納得、参考になった、ヘー) なるほど(納得、参考になった、ヘー) なるほど(納得、参考になった、ヘー) なるほど(納得、参考になった、ヘー) なるほど(納得、参考になった、ヘー) なるほど(納得、参考になった、ヘー) なるほど(納得、参考になった、ヘー) なるほど(納得、参考になった、ヘー) なるほど(納得、参考になった、ヘー) なるほど(納得、参考になった、ヘー) なるほど(納得、参考になった、ヘー) なるほど(納得、参考になった、ヘー)
かわいい かわいい かわいい かわいい かわいい
驚いた 驚いた

トラックバック(0件)

タイトル (本文) ブログ名/日時

トラックバック用URL help


自分のブログにトラックバック記事作成(会員用) help

タイトル
本 文

コメント(1件)

内 容 ニックネーム/日時
最初はわかった(^O^)

しかし次が意味分からん(>_<)

私はITや理系には向いていないのだな。


(今頃気が付いたのか(-o-;))
みっふぃー☆
2008/08/11 07:54

コメントする help

ニックネーム
本 文
ソフトウェア開発技術者試験対策(1) -オートマトンを考える- 今日もなんだかいい天気♪/BIGLOBEウェブリブログ
文字サイズ:       閉じる