■

　次の表は，入力記号の集合が{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

注意：桁がずれて表示されているときは以下のサイトを参考にして下さい。
レイアウトが崩れて見えます＠まぐまぐ　http://www.mag2.com/help/r109.htm

• • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • -

もちのにの答え：ウ

最初の状態を、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 となる。