問題
表は、入力記号の集合が {0, 1}、状態集合が {a, b, c, d} である有限オートマトンの状態遷移表である。長さ 3 以上の任意のビット列を左（上位ビット）から順に読み込んで最後まで読み込んで 110 で終わったものを受理するには、どの状態を受理状態とすればよいか。
選択肢
- 1a
- 2b
- 3c
- 4d
正解
3. c
詳しい解説を見る解説を閉じる
解説
状態遷移表をたどると、1 を読むと a・c からは b へ、b・d からは d へ遷移し、続けてもう一度 1 を読むと b からも d からも d へ遷移する。つまり直前の 2 ビットが「11」であれば、その時点の状態は必ず d になる。最後に 0 を読むと d から c へ遷移するので、110 で終わるビット列を読み終えたときの状態は、どの状態から始めても必ず c となる。よって受理状態は c でウが正解。（出典: 平成28年度 秋期 応用情報技術者試験 午前 問4）
一問一答
全400問を繰り返し学習