応用情報技術者試験 応用情報技術者試験 平成29年度秋期 午前 問2: 次の BNF において非終端記号 〈A〉 から生成される文字列はどれか。 〈R0〉 ::= 0｜3｜6｜9 〈R1〉 ::= 1｜4｜7 〈R2〉 ::= 2｜

正解

ア. 123

正答率 60.1%（869人中 522人が正解）

問題の解説

〈R0〉〈R1〉〈R2〉は、それぞれ3で割った余りが0、1、2になる数字を表す。〈A〉〈B〉〈C〉は、各桁の数字の和を3で割った余りが順に0、1、2になる文字列を生成するので、〈A〉は各桁の和が3の倍数になる文字列である。「123」は各桁の和が6で、〈A〉→〈A〉〈R0〉→〈B〉〈R2〉〈R0〉→〈R1〉〈R2〉〈R0〉と導出できる。

選択肢ごとの解説

• ア正しい。各桁の和が1+2+3=6で3の倍数になるので、〈A〉から生成される。
• イ各桁の和が1+2+4=7で、3で割った余りが1になるので、〈B〉の文字列であり、〈A〉からは生成されない。
• ウ各桁の和が1+2+7=10で、3で割った余りが1になるので、〈B〉の文字列である。
• エ各桁の和が1+2+8=11で、3で割った余りが2になるので、〈C〉の文字列である。