基本情報技術者試験 - 令和6年1月修了 - 問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〉
〈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 |
答え ： ア
分野 ： テクノロジ系 › 基礎理論 › 基礎理論 › 情報に関する理論
解説 ：
「BNF」（バッカス・ナウア記法）という，文法規則を表す記法についての問題です。BNFでは，ある記号（非終端記号）がどのような文字列に展開されるかをルールとして定義します。
問題文のルールを見ると，0・3・6・9のグループが「R0」，1・4・7のグループが「R1」，2・5・8のグループが「R2」としてまとめられています。さらにAは「R0」または「Aの後にR0」または「BREの後にR2」または「CREの後にR1」という形で定義されており，これは実質的に「3の倍数を表す数字列」を作るルールになっています。
選択肢「ア」123は各けたを足すと6になり3の倍数なので，Aから生成できます。「イ」124は各けたの和が7，「ウ」127は10，「エ」128は11で，いずれも3の倍数ではないため，Aからは生成されません。正解は「ア」です。このように，一見複雑なBNFの規則も，実際に数字を当てはめて規則性を見つけると理解しやすくなります。
分野 ： テクノロジ系 › 基礎理論 › 基礎理論 › 情報に関する理論
解説 ：
「BNF」（バッカス・ナウア記法）という，文法規則を表す記法についての問題です。BNFでは，ある記号（非終端記号）がどのような文字列に展開されるかをルールとして定義します。
問題文のルールを見ると，0・3・6・9のグループが「R0」，1・4・7のグループが「R1」，2・5・8のグループが「R2」としてまとめられています。さらにAは「R0」または「Aの後にR0」または「BREの後にR2」または「CREの後にR1」という形で定義されており，これは実質的に「3の倍数を表す数字列」を作るルールになっています。
選択肢「ア」123は各けたを足すと6になり3の倍数なので，Aから生成できます。「イ」124は各けたの和が7，「ウ」127は10，「エ」128は11で，いずれも3の倍数ではないため，Aからは生成されません。正解は「ア」です。このように，一見複雑なBNFの規則も，実際に数字を当てはめて規則性を見つけると理解しやすくなります。
共有ボタンをタップ