平成26年度 春期 午前 問3
基礎理論
BNFに関する問題
次の BNF において非終端記号 〈A〉 から生成される文字列はどれか。
〔BNF〕
〈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〉
- ア123
- イ124
- ウ127
- エ128
答えと解説を見る
✓ これが正解ア123
解説
各桁の和が 3 の倍数になる並びが生成できます。
設問は、BNF で書かれた規則から生成できる文字列を選ばせています。三桁でも導出の道は多いので総当たりはせず、終端記号の分け方から読むのが近道です。R0 は 0・3・6・9、R1 は 1・4・7、R2 は 2・5・8 で、3 で割った余りごとに数字が仕分けられています。その上で A・B・C の規則を見ると、右辺に並ぶ二つの記号が持つ余りの和が、そのまま左辺の番号になっています。A なら、A に R0 を続ける形で 0 と 0、B に R2 を続ける形で 1 と 2、C に R1 を続ける形で 2 と 1 となり、和はいつも 3 で割り切れます。A は各桁の和が 3 の倍数になる並び、B は余りが 1 の並び、C は余りが 2 の並びを表しているという不変量が見えます。123 は 1 と 2 と 3 を足して 6 ですから A から生成できます。末尾から剥がして確かめると、3 が R0、残る 12 は和が 3 で A、その 2 が R2、残る 1 が R1 で B となり、規則どおりに導けます。
ほかの選択肢はなぜ違うのか
- イ124：三つの数字を足すと 7 になり、3 で割れば 1 余ります。その余りを受け持つのは B の側です。末尾の 4 を切り離す規則は A の側にもありますが、その形では前半の 12 が C から出なければならず、12 は和が 3 で余りが 0 ですから C にはなりません。
- ウ127：三つの数字を足すと 10 になり、やはり 3 で割った余りは 1 です。124 と同じ仲間にあたるので、出どころは B のほうになります。
- エ128：三つの数字を足すと 11 で、3 で割った余りは 2 です。余り 2 を受け持つのは C ですから、A の側からは導き出せません。
出典：平成26年度 春期 応用情報技術者試験 午前 問3
この解説に誤りを見つけたら教えてください。直して、直した記録を残します。誤りを報告する（メールが開きます）