平成28年度 秋期
応用情報技術者試験問題と解答
問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のご相談なら ファーストマクロ 



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