問題プレビューID: f39ce313基本情報技術者試験 午前免除試験 2024年1月28日

問 3
基本情報技術者試験 午前免除試験 2024年1月28日

次の 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〉
解説

正解は「ア」です。

各非終端記号が生成する文字列は,その数字の並びを 3 で割った余りによって整理できます。〈R0〉は 3 の倍数(0,3,6,9),〈R1〉は 3 で割って 1 余る数(1,4,7),〈R2〉は 3 で割って 2 余る数(2,5,8)です。

  • 〈A〉は「3 で割った余りが 0」
  • 〈B〉は「3 で割った余りが 1」
  • 〈C〉は「3 で割った余りが 2」

となるように構成されています。例えば 〈A〉 ::= 〈B〉〈R2〉 は,余り 1 + 余り 2 = 3 ≡ 0 となり,〈A〉の条件と一致します。つまり 〈A〉が生成する文字列は,各けたの数字の和が 3 の倍数(= 3 で割り切れる数)になります。

各選択肢の数字の和を調べると,

  • ア: 1 + 2 + 3 = 6(3 の倍数)→ 生成できる。
  • イ: 1 + 2 + 4 = 7(3 で割って 1 余る)。
  • ウ: 1 + 2 + 7 = 10(3 で割って 1 余る)。
  • エ: 1 + 2 + 8 = 11(3 で割って 2 余る)。

123 は,例えば 〈A〉⇒〈A〉〈R0〉⇒〈B〉〈R2〉〈R0〉⇒〈R1〉〈R2〉〈R0〉 のように導出でき,〈A〉から生成される文字列です。

関連問題

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