基礎理論
基本情報技術者試験 科目A免除 修了試験 20160612 実施分 問4
図で表される有限オートマトンで受理される文字列はどれか。ここで，[太矢印付き円]は初期状態を，[二重円]は受理状態を表す。
状態遷移図。状態は5つ: S0(初期状態・太矢印が入る), S1, S2, S3(受理状態・二重円), S4。遷移: S0 -0-> S0(自己ループ), S0 -1-> S1, S1 -0-> S0, S1 -1-> S2, S2 -0-> S0, S2 -1-> S3, S3 -0-> S0, S3 -1-> S4, S4 -0,1-> S4(自己ループ)。
- ア 01011
- イ 01111
- ウ 10111
- エ 11110
出典：基本情報技術者試験 科目A免除 修了試験 20160612 実施分 問4
答えと解説を見る
正解：ウ
覚える知識
状態遷移図の読解
有限オートマトンは、入力列を最後まで読んだ時点で受理状態にあればその文字列を受理する。
この問題で必要なこと
初期状態から入力文字列を1文字ずつたどり、最後に受理状態にいるか調べる。図は末尾に1が3連続すれば受理状態S3にいるが、さらに1が続くとS4に落ちる。
ひっかけ
S3から1でS4へ進むことを見落とすと、末尾が1111の文字列も受理と誤認する。
この知識の出題：本試験系 4 回・免除試験 13 回（公開問題での観測値）