2017年03月24日

平成28年度秋期 応用情報技術者試験問題 問4

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


   ┌─┬─┐
   │0│1│
 ┌─┼─┼─┤
 │a│a│b│
 ├─┼─┼─┤
 │b│c│d│
 ├─┼─┼─┤
 │c│a│b│
 ├─┼─┼─┤
 │d│c│d│
 └─┴─┴─┘


 ア a   イ b   ウ c   エ d




【正解】 ウ

最後の110で終わる直前の状態がa〜dのいずれかが判らないので
それぞれの場合に分けて考える。

aの状態の時
a → 
 → b →  → d →  → c

bの状態の時
b →  → d →  → d →  → c

cの状態の時
c →  → b →  → d →  → c

dの状態の時
d →  → d →  → d →  → c

従って、いずれの場合でも c のどの状態を受理状態とすればよい。


EXCEL VBAのご相談なら ファーストマクロ 



posted by ファーストマクロ at 19:17| Comment(0) | H28秋応用情報技術者
この記事へのコメント
コメントを書く
お名前:

メールアドレス:

ホームページアドレス:

コメント: