基礎理論
基本情報技術者試験 科目A免除 修了試験 20181209 実施分 問3
表は，入力記号の集合が {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免除 修了試験 20181209 実施分 問3
答えと解説を見る
正解：ウ
覚える知識
状態遷移図の読解
有限オートマトンは、入力列を読み終えた時の状態が受理状態なら受理する。
この問題で必要なこと
状態遷移表を追い、110を読み終えた時に必ず到達する状態を受理状態とする。1,1,0の順に読むと cに行く。
ひっかけ
他の状態は110以外の末尾(例:10,11)でも到達する状態を選ばせる。
この知識の出題：本試験系 4 回・免除試験 13 回（公開問題での観測値）