基礎理論
基本情報技術者試験 科目A免除 修了試験 20121216 実施分 問4
図で表される有限オートマトンで受理される文字列はどれか。ここで，→○は初期状態を，◎は受理状態を表す。
状態遷移図。5状態。S0（初期状態・左）、S1（上）、S2（右）、S3（受理状態・二重丸・下）、S4（右下）。遷移: S0→S0 (0)、S0→S1 (1)、S1→S0 (0)、S1→S2 (1)、S2→S0 (0)、S2→S3 (1)、S3→S0 (0)、S3→S4 (1)、S4→S4 (0,1)。
- ア 01011
- イ 01111
- ウ 10111
- エ 11110
出典：基本情報技術者試験 科目A免除 修了試験 20121216 実施分 問4
答えと解説を見る
正解：ウ
覚える知識
状態遷移図の読解
有限オートマトンは、入力列をたどって終了時に受理状態にいれば、その文字列を受理する。
この問題で必要なこと
初期状態S0から入力列に従って遷移をたどり、最後に受理状態S3にいる文字列を選ぶ。10111はS0→S1→S0→S1→S2→S3で受理される。
ひっかけ
途中でS3を通っても最後にS4へ遷移して受理されない文字列を混ぜている。
この知識の出題：本試験系 4 回・免除試験 13 回（公開問題での観測値）