応用情報技術者 2014年 春期 午前2 問03
問題文
次のBNFにおいて非終端記号〈A〉から生成される文字列はどれか。
〈〉 ::=0.3|6|9
〈〉 ::=1|4|7
〈〉 ::=2|5|8
〈〉 ::=〈〉|〈〉〈〉|〈〉〈〉|〈〉〈〉
〈〉 ::=〈〉|〈〉〈〉|〈〉〈〉|〈〉〈〉
〈〉 ::=〈〉|〈〉〈〉|〈〉〈〉|〈〉〈〉
選択肢
ア：123（正解）
イ：124
ウ：127
エ：128
BNFによる文字列生成問題【午前2 解説】
要点まとめ
- 結論：非終端記号〈A〉から生成される文字列は「123」であるため、正解はアです。
- 根拠：BNFの定義から〈A〉は〈R_0〉、〈B〉〈R_2〉、〈C〉〈R_1〉などの組み合わせで構成され、数字の組み合わせを順にたどると「123」が生成可能です。
- 差がつくポイント：BNFの再帰的な定義を正しく展開し、各非終端記号が生成する数字の範囲を理解することが重要です。
正解の理由
〈A〉は〈R_0〉、〈A〉〈R_0〉、〈B〉〈R_2〉、〈C〉〈R_1〉のいずれかで生成されます。
〈R_0〉は {0,3,6,9}、〈R_1〉は {1,4,7}、〈R_2〉は {2,5,8} です。
選択肢「123」は、〈A〉→〈B〉〈R_2〉の形で、〈B〉が「1」（〈R_1〉）を生成し、〈R_2〉が「2」を生成、さらに〈A〉が「3」（〈R_0〉）を生成する連鎖で可能です。
他の選択肢はBNFの規則に合致しません。
〈R_0〉は {0,3,6,9}、〈R_1〉は {1,4,7}、〈R_2〉は {2,5,8} です。
選択肢「123」は、〈A〉→〈B〉〈R_2〉の形で、〈B〉が「1」（〈R_1〉）を生成し、〈R_2〉が「2」を生成、さらに〈A〉が「3」（〈R_0〉）を生成する連鎖で可能です。
他の選択肢はBNFの規則に合致しません。
よくある誤解
BNFの再帰定義を無視して単純に数字を並べるだけで判断しがちです。
また、各非終端記号が生成する数字の集合を混同しやすい点も注意が必要です。
また、各非終端記号が生成する数字の集合を混同しやすい点も注意が必要です。
解法ステップ
- 〈R_0〉、〈R_1〉、〈R_2〉が生成する数字の集合を確認する。
- 〈A〉の定義を展開し、どのような文字列が生成可能かを考える。
- 〈B〉と〈C〉の定義も確認し、〈A〉からの展開に使える文字列を把握する。
- 選択肢の数字列がBNFの規則に従って生成可能か検証する。
- 生成可能な文字列が「123」であることを確認し、正解を決定する。
選択肢別の誤答解説
- イ（124）：4は〈R_1〉にあるが、「124」の順序で〈A〉から生成するのは不可能。
- ウ（127）：7は〈R_1〉にあるが、「127」の順序で〈A〉から生成できない。
- エ（128）：8は〈R_2〉にあるが、「128」の順序で〈A〉から生成できない。
- ア（123）：〈B〉が「1」、〈R_2〉が「2」、〈R_0〉が「3」を生成し、BNFの規則に合致。
補足コラム
BNF（Backus-Naur Form）は文法を形式的に表現する方法で、プログラミング言語の構文解析や形式言語理論で広く使われます。
非終端記号の再帰的定義を正しく理解することが、問題解決の鍵となります。
非終端記号の再帰的定義を正しく理解することが、問題解決の鍵となります。
FAQ
Q: 〈A〉が再帰的に定義されている場合、どうやって展開すればよいですか？
A: まず基本の生成規則を確認し、再帰部分は具体的な文字列に置き換えながら段階的に展開します。
A: まず基本の生成規則を確認し、再帰部分は具体的な文字列に置き換えながら段階的に展開します。
Q: 〈B〉や〈C〉の定義も複雑ですが、どう扱えばよいですか？
A: それぞれの非終端記号が生成する数字の集合を把握し、〈A〉の展開にどう関わるかを考えます。
A: それぞれの非終端記号が生成する数字の集合を把握し、〈A〉の展開にどう関わるかを考えます。
関連キーワード: BNF, 文法解析、非終端記号、再帰定義、形式言語
\ せっかくなら /
応用情報技術者を
クイズ形式で学習しませんか？
クイズ画面へ遷移する→
すぐに利用可能！