問題プレビューID: efcfe940応用情報技術者試験 2014年(平成26年度)春期 午前

問 3
応用情報技術者試験 2014年(平成26年度)春期 午前

次の BNF において非終端記号 ⟨A⟩ から生成される文字列はどれか。

⟨R0⟩ ::= 0 | 3 | 6 | 9
⟨R1⟩ ::= 1 | 4 | 7
⟨R2⟩ ::= 2 | 5 | 8
⟨A⟩  ::= ⟨R0⟩ | ⟨A⟩⟨R0⟩ | ⟨B⟩⟨R2⟩ | ⟨C⟩⟨R1⟩
⟨B⟩  ::= ⟨R1⟩ | ⟨A⟩⟨R1⟩ | ⟨B⟩⟨R0⟩ | ⟨C⟩⟨R2⟩
⟨C⟩  ::= ⟨R2⟩ | ⟨A⟩⟨R2⟩ | ⟨B⟩⟨R1⟩ | ⟨C⟩⟨R0⟩
解説

正解は「ア」です。

非終端記号 ⟨A⟩,⟨B⟩,⟨C⟩ から生成される文字列は,それぞれ「けたの和を 3 で割った余りが 0,1,2」になるものに対応しています。

  • ⟨R0⟩ = {0, 3, 6, 9} は 3 で割った余りが 0,⟨R1⟩ = {1, 4, 7} は余り 1,⟨R2⟩ = {2, 5, 8} は余り 2 の数字です。
  • ⟨A⟩ ::= ⟨R0⟩ | ⟨A⟩⟨R0⟩ | ⟨B⟩⟨R2⟩ | ⟨C⟩⟨R1⟩ であり,右辺はいずれも「それまでの余りに次の数字の余りを足すと 0 になる」組合せになっています。つまり ⟨A⟩ は各けたの和が 3 の倍数になる文字列を生成します。

各選択肢のけたの和は,ア 123 → 1+2+3 = 6,イ 124 → 7,ウ 127 → 10,エ 128 → 11 です。6 は 3 の倍数なので,⟨A⟩ から生成されるのは 123 の ア です。

関連問題

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