平成20年春期試験午前問題 問11

午前試験免除制度対応!基本情報技術者試験のeラーニング【独習ゼミ】
次のBNFで定義されるビット列Sであるものはどれか。

  <S> ::= 01|0<S>1

  • 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」とわかります。

Pagetop