基礎理論
平成28年度 春期 基本情報技術者試験 午前 問2
次の状態遷移図で表現されるオートマトンで受理されるビット列はどれか。ここで，ビット列は左から順に読み込まれるものとする。
状態遷移図。3 状態が左から右に並ぶ。左の状態が初期状態（太い矢印が入る）で，自己ループのラベルは 0。左の状態から中央の状態へ 1 で遷移。中央の状態の自己ループのラベルは 1。中央の状態から右の状態へ 0 で遷移。右の状態は二重丸（受理状態）で，自己ループのラベルは 0, 1。
- ア 0000
- イ 0111
- ウ 1010
- エ 1111
出典：平成28年度 春期 基本情報技術者試験 午前 問2
答えと解説を見る
正解：ウ
覚える知識
状態遷移図の読解
オートマトンは、入力列を初期状態から順に読み、受理状態に到達して終わる列を受理する。
この問題で必要なこと
初期状態から入力ビットを順にたどり、最終的に受理状態(二重丸)で終わるビット列を選ぶ。本問は「0*1 1* 0 (0|1)*」の形で、1の後に0が現れる列が受理される。
ひっかけ
1だけの列(エ)や0だけの列(ア)は受理状態に到達しない点を見落とさせる。
この知識の出題：本試験系 4 回・免除試験 13 回（公開問題での観測値）