基礎理論
基本情報技術者試験 科目A免除 修了試験 20250126 実施分 問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免除 修了試験 20250126 実施分 問3
答えと解説を見る
正解：ウ
覚える知識
状態遷移表による文字列検査
有限オートマトンは入力列に応じて状態を遷移し、受理状態で終われば入力列を受理する。
この問題で必要なこと
状態遷移表を追い、直近3文字が110で終わるときに到達する状態を特定する。110で終わる入力は、1→1→0と進んだ末にcへ至る(b,dから0でc)。ただしb,dにはそれぞれ入力10・110以外でも到達しうる点に注意し、cへの遷移条件は「直前が0で、その前が1」である。
ひっかけ
b,dのように1で終わる状態や、aのように0が連続した状態を受理状態と取り違えさせる。
この知識の出題：本試験系 2 回・免除試験 5 回（公開問題での観測値）