問 題
次の表は、入力記号の集合が {0、1}、状態集合が {a、b、c、d、e} である有限オートマトンの状態遷移表である。この有限オートマトンが、長さ 3 以上の任意のビット列を左から順に読み込んで最後が 110 で終わるものを受理するとした場合、受理状態はどれか。
1．a
2．b
3．c
4．d
5．e
正解 (4)
解 説
「最後が 110 で終わるものを受理する」ということから、それ以前にどの状態にあったとしても、110 を受け取った結果、たった一つの状態に落ち着くと考えられます。そこで「状態 a にいて 110 を受け取るとどこに行くか？状態 b だと？というのを 5 パターン考えれば正解がわかる」と考えます。
a：→ b → e → d
b：→ e → b → d
c：→ a → b → d
d：→ a → b → d
e：→ b → e → d です。全て 状態 d にいきます。
以上より、正解は 4 です。
類題 H27no33
コメント