応用情報技術者 2017年 秋期 午前2 問02

BNFによる文字列生成問題【午前2 解説】

要点まとめ

• 結論：非終端記号〈A〉から生成される文字列は「123」である。
• 根拠：〈A〉は〈R_0〉、〈B〉〈R_2〉、〈C〉〈R_1〉など複数の規則を持ち、数字の組み合わせを解析すると「123」が生成可能。
• 差がつくポイント：BNFの展開順序と非終端記号の定義を正確に理解し、各規則の数字集合を正しく把握することが重要。

正解の理由

1. 〈R_0〉：0,3,6,9
2. 〈A〉〈R_0〉：〈A〉の文字列に0,3,6,9を付加
3. 〈B〉〈R_2〉
4. 〈C〉〈R_1〉

• 〈R_0〉 = {0,3,6,9}
• 〈R_1〉 = {1,4,7}
• 〈R_2〉 = {2,5,8}

よくある誤解

• 〈A〉が単に〈R_0〉の数字だけを生成すると誤解しがちです。
• 〈B〉や〈C〉の定義を無視して数字の組み合わせを考えると誤答になります。

解法ステップ

1. 〈R_0〉、〈R_1〉、〈R_2〉の数字集合を確認する。
2. 〈A〉の生成規則を読み解き、どの非終端記号がどの数字を生成するか把握する。
3. 〈B〉と〈C〉の定義を展開し、それぞれが生成可能な数字を確認する。
4. 選択肢の数字列が〈A〉から生成可能かを検証する。
5. 生成可能な文字列が「123」であることを確認し、選択肢アを選ぶ。

選択肢別の誤答解説

• イ（124）：4は〈R_1〉にあるが「124」の順序で〈A〉から生成できない。
• ウ（127）：7は〈R_1〉にあるが「127」の順序で〈A〉から生成できない。
• エ（128）：8は〈R_2〉にあるが「128」の順序で〈A〉から生成できない。

補足コラム

FAQ