基礎理論
平成30年度 春期 基本情報技術者試験 午前 問4
入力記号，出力記号の集合が {0, 1} であり，状態遷移図で示されるオートマトンがある。0011001110 を入力記号とした場合の出力記号はどれか。ここで，S1 は初期状態を表し，グラフの辺のラベルは，入力/出力を表している。
〔状態遷移図〕状態 S1（初期状態，矢印で示される），S2，S3。遷移（入力/出力）: S1→S1 は 0/0（自己ループ），S1→S2 は 1/0，S2→S1 は 0/0，S2→S3 は 1/1，S3→S3 は 1/1（自己ループ），S3→S1 は 0/0。
- ア 0001000110
- イ 0001001110
- ウ 0010001000
- エ 0011111110
出典：平成30年度 春期 基本情報技術者試験 午前 問4
答えと解説を見る
正解：ア
覚える知識
状態遷移図の読解
状態遷移図は状態と、入力/出力のラベルが付いた遷移で構成され、入力列に沿って辿ることで出力列が決まる。
この問題で必要なこと
初期状態S1から入力を1文字ずつ辿り、遷移ごとの出力を並べる。S1で0なら0出力で留まり、1なら0出力でS2へ。S2で1なら1出力でS3へ。S3で1の間は1出力、0で0出力してS1へ戻る。
ひっかけ
S3から0でS1に戻るときの出力を1と取り違える、S2での入力0の遷移を見落とす。
この知識の出題：本試験系 4 回・免除試験 13 回（公開問題での観測値）