基礎理論
基本情報技術者試験 科目A免除 修了試験 201007 実施分 問4
図で表される有限オートマトンで受理される文字列はどれか。ここで，→○ は初期状態を，◎ は受理状態を表す。
状態は5個: S0（初期状態・左），S1（上），S2（右），S3（受理状態・二重丸・下中央），S4（右下，0,1で自己ループ）。
遷移: 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免除 修了試験 201007 実施分 問4
答えと解説を見る
正解：ウ
覚える知識
状態遷移図の読解
有限オートマトンは、入力列を辿った終了時点で受理状態にあればその文字列を受理する。
この問題で必要なこと
初期状態から入力文字列を1文字ずつ遷移させ、最後に受理状態にいるかを確認する。10111はS0→S1→S0→S1→S2→S3で受理される。
ひっかけ
途中でS3やS4に入る経路を見落とす、または途中の状態を最終状態と混同する。
この知識の出題：本試験系 4 回・免除試験 13 回（公開問題での観測値）