情報に関する理論 (全41問中28問目)
No.28
次のBNFで定義されるビット列Sであるものはどれか。
<S> ::＝ 01|0<S>1
<S> ::＝ 01|0<S>1
出典：平成20年春期 問11
- 000111
- 010010
- 010101
- 011111
分類
テクノロジ系 » 基礎理論 » 情報に関する理論
正解
ア
解説
BNF(Backus-Naur Form，バッカス・ナウア記法)は、コンピュータ言語の構文などを記述するために使用される表記法で、プログラム言語ALGOL(アルゴル)の文法を表現するためにジョン・バッカスなどによって考案されました。
「::＝」は等号「|」は論理和(OR)を表しているので、問題文のBNFは「<S>は、01または0<S>1である」と解釈します。また<S>は両辺に表れているので再帰的に定義されていることになります。
<S>に右辺のいずれかを代入していくと、
<S>→0<S>1→00<S>11→000111
というように定義できることができるのは「000111」とわかります。
「::＝」は等号「|」は論理和(OR)を表しているので、問題文のBNFは「<S>は、01または0<S>1である」と解釈します。また<S>は両辺に表れているので再帰的に定義されていることになります。
<S>に右辺のいずれかを代入していくと、
<S>→0<S>1→00<S>11→000111
というように定義できることができるのは「000111」とわかります。