本文へスキップ

技術士試験(情報工学部門)・情報技術者試験。ファーストマクロ。


Since 2016.4.19

平成26年度 春期 高度情報技術者試験問題と解説

問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 → 1 → b → 1 → d → 0 → c

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

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

dの状態の時
 d → 1 → d → 1 → d → 0 → c

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

問1 目次 問3