2019年国家一般職(電気・電子・情報) No.33解説

　問題　　　　　

表は、入力記号の集合が {0、1}、状態集合が {a、b、c、d} である有限オートマトンの状態遷移表である。受理状態を b とするとき、この有限オートマトンが受理する入力記号列として最も妥当なのは次のうちではどれか。

1．001 で終わる全ての記号列
2．010 で終わる全ての記号列
3．011 で終わる全ての記号列
4．100 で終わる全ての記号列
5．110 で終わる全ての記号列

正解 (2)

　解説　　　　　

表の読み方は「状態が a だったら、入力 0 の場合状態 c へ、入力 1 だったら a のままでいてください」といったものです。各状態と入力に応じた変化が示されています。

有限オートマトンでは「入力が終了した時に受理状態　であれば『OK,受理しよう』という判断をする」というのが前提知識となります。すると、入力の本当に最後の 1 個は「受理状態である b に遷移する入力」でなければいけません。表を見てみると b に遷移しうるのは 0 のみです。

そのため、最後が 1 ではだめです。選択肢 1,3 は誤りとわかります。

また、表より「最後の入力の 1 つの前の状態が c か d」である必要があります。選択肢を検討してみると、…010 であれば、それまでの状態がどう遷移していようと、以下のように 入力最後の 1 つ前に状態 d に遷移します。その結果、最後の 0 で状態 b に遷移してくれます。

以上より、正解は 2 です。

コメント