平成28年度 秋期
高度情報技術者試験問題と解答
問2
表は、入力記号の集合が {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のご相談なら ファーストマクロ 



問1 目次 問3
ファーストマクロ TOPページ