平成26年度春期 応用情報技術者試験 午前 問3
次の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〉
- ア 123
- イ 124
- ウ 127
- エ 128
解答・解説を見る
正解：ア
AI解説
このBNFは各桁を3で割った余りで分類している。〈R0〉は余り0の数字(0,3,6,9),〈R1〉は余り1(1,4,7),〈R2〉は余り2(2,5,8)であり,〈A〉は桁の余りの合計が3で割り切れる文字列,〈B〉は余り1,〈C〉は余り2の文字列を生成する。つまり〈A〉が生成するのは各桁の和が3の倍数,すなわち3の倍数を表す文字列である。123は1+2+3=6で3の倍数なので〈A〉から生成できる。 ア: 正解。123は桁の和が1+2+3=6で3の倍数であり,〈A〉から導出できる(例:1は〈B〉,12は1(余り1)+2(余り2)で余り0の〈A〉,123は〈A〉〈R0〉で〈A〉となる)。 イ: 124は桁の和が7で3で割ると余り1,〈A〉ではなく〈B〉から生成される文字列である。 ウ: 127は桁の和が10で余り1,これも〈B〉から生成される文字列である。 エ: 128は桁の和が11で余り2,〈C〉から生成される文字列である。 💡 R0/R1/R2が「3で割った余り」の数字グループだと気づくのが最短ルート。〈A〉=余り0,〈B〉=余り1,〈C〉=余り2の状態をもつオートマトンと見れば,答えは桁和が3の倍数の選択肢だけである。
出典：平成26年度 春期 応用情報技術者試験 午前 問3 ／ 独立行政法人情報処理推進機構（IPA）
※Web掲載用に表記を一部変更しています。著作権はIPAに帰属します。
※Web掲載用に表記を一部変更しています。著作権はIPAに帰属します。