表は、入力記号の集合が {0，1}、状態集合が {a，b，c，d} である有限オートマトンの状態遷移表である。長さ3以上の任意のビット列を左
(上位ビット) から順に読み込んで最後が110で終わっているものを受理するには、どの状態を受理状態とすればよいか。
┌─┬─┐
│０│１│
┌─┼─┼─┤
│ａ│ａ│ｂ│
├─┼─┼─┤
│ｂ│ｃ│ｄ│
├─┼─┼─┤
│ｃ│ａ│ｂ│
├─┼─┼─┤
│ｄ│ｃ│ｄ│
└─┴─┴─┘
ア 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 の状態を受理状態とすればよい。
| 問３ | 目次 | 問５ |