分野：テクノロジ系
中分類：基礎理論
小分類：情報に関する理論

BNF(Backus-Naur Form，バッカス・ナウア記法)は、コンピュータ言語の構文などを記述するために使用される表記法で、プログラム言語ALGOL(アルゴル)の文法を表現するためにジョン・バッカスなどによって考案されました。

「::＝」は等号「|」は論理和(OR)を表しているので、問題文のBNFは「<S>は、01または0<S>1である」と解釈します。また<S>は両辺に表れているので再帰的に定義されていることになります。
<S>に右辺のいずれかを代入していくと、

　<S>→0<S>1→00<S>11→000111

というように定義できることができるのは「000111」とわかります。