平成29年度 秋期 午前 問2
基礎理論
BNFに関する問題
次の BNF において非終端記号 ＜A＞ から生成される文字列はどれか。
＜R₀＞ ::= 0 | 3 | 6 | 9 ＜R₁＞ ::= 1 | 4 | 7 ＜R₂＞ ::= 2 | 5 | 8 ＜A＞ ::= ＜R₀＞ | ＜A＞＜R₀＞ | ＜B＞＜R₂＞ | ＜C＞＜R₁＞ ＜B＞ ::= ＜R₁＞ | ＜A＞＜R₁＞ | ＜B＞＜R₀＞ | ＜C＞＜R₂＞ ＜C＞ ::= ＜R₂＞ | ＜A＞＜R₂＞ | ＜B＞＜R₁＞ | ＜C＞＜R₀＞
- ア123
- イ124
- ウ127
- エ128
答えと解説を見る
✓ これが正解ア123
解説
桁の和を 3 で割った余りが 0 の数字列が当てはまります。
設問は、与えられた生成規則から作れる文字列を選ばせています。定義を四本とも展開していくと手間がかかるので、まず終端記号の三つのまとまりを見ます。0・3・6・9 は 3 で割った余りが 0、1・4・7 は余りが 1、2・5・8 は余りが 2 の数字で、添字がそのまま余りを表しています。そこで、非終端記号のほうも桁の和の余りを表していると仮定して、九本の生成規則に当てはめてみます。余り 0 の後ろに余り 0 を足せば 0、余り 1 の後ろに余り 2 を足せば 3 で余りは 0、というように、九本すべてが仮定と食い違いません。よって問われている記号から作れるのは、桁の和を 3 で割った余りが 0 になる数字列です。あとは各候補の桁を足すだけで決まります。
ほかの選択肢はなぜ違うのか
- イ124：各位を足すと 7 で、3 で割ると 1 が残ります。末尾の 4 は余り 1 のまとまりに属する数字なので、余りが 0 の並びにはならず、別の記号から導かれる側に入ります。
- ウ127：各位の合計は 10 で、こちらも 3 で割ると 1 が残ります。末尾の 7 も余り 1 の数字なので、前半までの余りに足しても 0 へは戻りません。
- エ128：各位の合計は 11 で、3 で割った残りは 2 です。余り 2 を担当する記号の側に属する並びなので、問われている記号の定義には現れてきません。
出典：平成29年度 秋期 応用情報技術者試験 午前 問2
この解説に誤りを見つけたら教えてください。直して、直した記録を残します。誤りを報告する（メールが開きます）