問 題
次の㋐～㋔の記号列のうち，図のような有限オートマトンで受理される記号列のみを全て挙げているのはどれか。ただし，太い矢印が示す状態は初期状態を，二重丸で表された状態は受理状態をそれぞれ表す。
㋐ 000110110100111
㋑ 001011001111011
㋒ 011001100110001
㋓ 011101010110111
㋔ 110110111110110
1．㋐
2．㋐，㋒
3．㋑，㋒，㋔
4．㋑，㋓
5．㋓，㋔
正解 (2)
解 説
初期状態から時計回りに状態1,状態2,状態3,状態4、 一つだけ右下に離れている状態を 状態 5 とおきます。記号列は 頭から、すなわち左端から読んでいきます。㋐であれば、0 からです。
㋐の記号列を順に読んでいくと、状態はまず、初期状態から 0 を読んで、状態 1 のまま。以下→1 → 1 → 1 → 2 → 3 → 3 → 4 → 1 → 1 → 2 → 1 → 1 → 2 → 3 → 4 と状態遷移します。最後が受理状態である状態４なので、受理されます。よって、㋐ は OK です。正解は 1 or 2 です。
㋒の記号列を順に読んでいくと、状態は 初期状態 → 1 → 2 → 3 → 3 → 3 → 4 → 1 → 1 → 1 → 2 → 3 → 3 → 3 → 3 → 4 と状態遷移します。やはり最後が受理状態である状態 4 なので、受理されます。㋒もOKです。
以上より、正解は 2 です。
類題H29no33
コメント