BNF で生成される文字列
出典: 平成29年度 秋期 応用情報技術者試験 午前 問2 (IPA)
次の 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 は各桁の和が 6 で 3 の倍数なので、〈A〉 から生成されます。正しい答えです。
- イ: 124 は各桁の和が 7 で、3 で割ると 1 余るので 〈B〉 の文字列です。
- ウ: 127 は各桁の和が 10 で、3 で割ると 1 余るので 〈B〉 の文字列です。
- エ: 128 は各桁の和が 11 で、3 で割ると 2 余るので 〈C〉 の文字列です。
ポイント
- 〈R₀〉 は 3 で割った余りが 0、〈R₁〉 は余り 1、〈R₂〉 は余り 2 の数字です。
- 〈A〉〈B〉〈C〉 は、それまでの数字列を 3 で割った余りが 0・1・2 の状態を表しています。例えば 〈B〉〈R₂〉 は「余り 1 の後に余り 2 の数字が続く → 余り 0」なので 〈A〉 になります。
- つまり 〈A〉 から生成されるのは 3 の倍数 です。各桁の和が 3 の倍数かどうかで判定できます。
- 123 は 1 ＋ 2 ＋ 3 = 6 で 3 の倍数です。