情報に関する理論 (全41問中21問目)
No.21
次の規則から生成することができる式はどれか。
〔規則〕
＜式＞ ::＝＜変数＞｜(＜式＞＋＜式＞)｜＜式＞＊＜式＞
＜変数＞ ::＝A｜B｜C｜D
〔規則〕
＜式＞ ::＝＜変数＞｜(＜式＞＋＜式＞)｜＜式＞＊＜式＞
＜変数＞ ::＝A｜B｜C｜D
出典：平成23年秋期 問4
- A＋(B＋C)＊D
- (A＋B)＋(C＋D)
- (A＋B)＊(C＋D)
- (A＊B)＋(C＊D)
分類
テクノロジ系 » 基礎理論 » 情報に関する理論
正解
ウ
解説
問題文のような構文定義法は、BNF(Backus-Naur Form，バッカス・ナウア記法)と呼ばれ、XMLをはじめ多くのプログラム言語の構文定義に用いられています。
BNFで使われている各記号は、「::＝」が左辺と右辺の区切り、「｜」がor(または)、「＜＞」は非終端記号を表しています。
各式を規則に従って変換していき、最後に<式>の形になれば構文定義に則っていることになります。
BNFで使われている各記号は、「::＝」が左辺と右辺の区切り、「｜」がor(または)、「＜＞」は非終端記号を表しています。
各式を規則に従って変換していき、最後に<式>の形になれば構文定義に則っていることになります。
- A＋(B＋C)＊D → <式>＋<式>＊<式> → <式>＋<式>
- (A＋B)＋(C＋D) → <式>＋<式>
- 正しい。以下のように、これだけが＜式＞になります。
(A＋B)＊(C＋D) → <式>＊<式> → <式> - (A＊B)＋(C＊D) → (<式>)＋(<式>)