平成29年度秋期 応用情報技術者試験 午前 問2
次の 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〉〈R1〉〈R2〉は余りが0,1,2の数字、〈A〉〈B〉〈C〉は桁の和の余りが0,1,2の数字列を生成する。〈A〉から生成されるのは桁の和が3の倍数の文字列であり、1+2+3=6となる123が該当する。実際、1は〈R1〉→〈B〉、〈B〉〈R2〉→12は〈A〉、〈A〉〈R0〉→123は〈A〉と導出できる。 ア: 正解。桁の和6は3で割り切れ、〈A〉から導出できる。 イ: 124は桁の和7(余り1)で〈B〉から生成される文字列であり、〈A〉からは生成されない。 ウ: 127は桁の和10(余り1)で〈B〉に属し、〈A〉からは生成されない。 エ: 128は桁の和11(余り2)で〈C〉に属し、〈A〉からは生成されない。 💡 3つの非終端記号が相互参照するBNFを見たら「3で割った余りの状態遷移(オートマトン)」を疑う。時間がなければ各選択肢を実際に導出して確かめるのが確実。
出典：平成29年度 秋期 応用情報技術者試験 午前 問2 ／ 独立行政法人情報処理推進機構（IPA）
※Web掲載用に表記を一部変更しています。著作権はIPAに帰属します。
※Web掲載用に表記を一部変更しています。著作権はIPAに帰属します。