基本情報技術者平成20年春期 午前問11

午前問11

次のBNFで定義されるビット列Sであるものはどれか。

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

分類

テクノロジ系 » 基礎理論 » 情報に関する理論

正解

解説

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

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

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

というように定義できることができるのは「000111」とわかります。
© 2010-2021 基本情報技術者試験ドットコム All Rights Reserved.

Pagetop