表は、入力記号の集合が {0，1}、状態集合が {a，b，c，d} である
有限オートマトンの状態遷移表である。長さ３以上の任意のビット列を
左 (上位ビット) から順に読み込んで最後が１１０で終わっているものを
受理するには、どの状態を受理状態とすればよいか。
┌─┬─┐
│０│１│
┌─┼─┼─┤
│ａ│ａ│ｂ│
├─┼─┼─┤
│ｂ│ｃ│ｄ│
├─┼─┼─┤
│ｃ│ａ│ｂ│
├─┼─┼─┤
│ｄ│ｃ│ｄ│
└─┴─┴─┘
ア ａ イ ｂ ウ ｃ エ ｄ
最後の１１０で終わる直前の状態がａ～ｄのいずれかが判らないので
それぞれの場合に分けて考える。
ａの状態の時
ａ → １ → ｂ → １ → ｄ → ０ → ｃ
ｂの状態の時
ｂ → １ → ｄ → １ → ｄ → ０ → ｃ
ｃの状態の時
ｃ → １ → ｂ → １ → ｄ → ０ → ｃ
ｄの状態の時
ｄ → １ → ｄ → １ → ｄ → ０ → ｃ
従って、いずれの場合でも ｃ のどの状態を受理状態とすればよい。
EXCEL ＶＢＡのご相談なら ファーストマクロ へ
タグ：有限オートマトン
