基本情報技術者試験 基本情報技術者試験 令和2年度 科目A 修了認定試験 午前 問5: 図は、偶数個の 1 を含むビット列を受理するオートマトンの状態遷移図であり、二重丸が受理状態を表す。a、b の適切な組合せはどれか。 （状態：偶（受理／初期）、

問題本文

図は、偶数個の 1 を含むビット列を受理するオートマトンの状態遷移図であり、二重丸が受理状態を表す。a、b の適切な組合せはどれか。 （状態：偶（受理／初期）、奇。0 で偶→偶（自己ループ）、1 で偶→奇（ラベル a）、b で奇→奇 …省略）

選択肢

• ア.a=0, b=0
• イ.a=0, b=1
• ウ.a=1, b=0
• エ.a=1, b=1

正解

ウ. a=1, b=0

解説

状態「偶」で「1」を入力すると「奇」に遷移する（ラベル a=1）。状態「奇」で「0」を入力すると「奇」のまま自己ループする（ラベル b=0）。よって a=1, b=0。