基礎理論
基本情報技術者試験 科目A免除 修了試験 20260125 実施分 問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免除 修了試験 20260125 実施分 問3
答えと解説を見る
正解：ウ
覚える知識
状態遷移図の読解
有限オートマトンは、入力を1つずつ読んで状態遷移し、受理状態で終われば列を受理する。
この問題で必要なこと
状態遷移表を追い、末尾が110になったときにだけ到達する状態を見つける。'11'の後に0を読むと状態cになる。
ひっかけ
状態bやdを選ばせる。bは直前が1の状態で、dは'11'を読んだ状態にすぎない。
この知識の出題：本試験系 4 回・免除試験 13 回（公開問題での観測値）