問題プレビューID: 045dd7d9基本情報技術者試験 午前免除試験 2021年1月24日

問 5
基本情報技術者試験 午前免除試験 2021年1月24日

図は,偶数個の 1 を含むビット列を受容するオートマトンの状態遷移図であり,二重丸が受容状態を表す。a,b の適切な組合せはどれか。

(「偶」は受容状態(二重丸),「奇」は非受容状態である。)

Label

a

b

ア

0

0

イ

0

1

ウ

1

0

エ

1

1

解説

正解は「ウ」です。

状態「偶」はここまでに読んだ 1 の個数が偶数であること,「奇」は奇数であることを表します。

  • 入力が 0 のときは 1 の個数が変わらないので,状態は遷移しません。したがって「偶」の自己ループが 0 であることと整合し,「奇」の自己ループ b も 0 です。
  • 入力が 1 のときは偶奇が反転します。「偶」から「奇」への遷移が 1 であることと同様に,「奇」から「偶」への遷移 a も 1 です。

よって a = 1,b = 0 の「ウ」が正解です。

  • ア: a = 0 とすると,1 を読んでも「奇」から「偶」へ戻れず,偶数個の 1 を受容できません。
  • イ: a = 0 であり,同様に誤りです。
  • エ: b = 1 とすると,0 を読んだときに状態が遷移してしまい,1 の個数が変わらないという前提に反します。

関連問題

本文が同じ・似ている問題を表示しています