有限オートマトンの受理状態
出典: 平成28年度 秋期 応用情報技術者試験 午前 問4 (IPA)
表は，入力記号の集合が {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
正解と解説を見る
正解: ウ
- ア: a は、最後が 00 や 100 などで終わったときの状態です。
- イ: b は、最後が 01 で終わったときの状態です。
- ウ: 最後が 110 で終わると、どこから始めても必ず c にいるので正しい答えです。
- エ: d は、最後が 11 で終わったときの状態です。
ポイント
最後の 3 ビットが 110 になったときにいる状態を調べます。
- どの状態でも、1 を読むと b か d に移ります。
- b でも d でも、次に 1 を読むと d に移ります。
- d で 0 を読むと c に移ります。
よって 110 で終わったときは必ず c にいるので、c を受理状態にします。