2008年春科目A
アルゴリズムとプログラミングの過去問

まずは自分で考えて、理由を確かめよう。

LET'S TRY

次のBNFで定義されるビット列Sはどれか。<S> ::= 01|0<S>1

当てはまるものを、ひとつ選んでね。

1〜4キーで選択し、Enterキーで採点できます。

ア

000111

イ

010010

ウ

010101

エ

011111

LET'S UNDERSTAND

キホン猫と、理由を確かめよう。

自分で考えてから、解説を開いてみてね。

正解と解説を見る

正解はアです。

BNFの規則は<S>が「01」または「0<S>1」で定義される再帰定義。<S>→0<S>1→0(0<S>1)1→0(0(01)1)1=000111。再帰的に適用すると長さ2n（n≧1）のビット列で前半がすべて0，後半がすべて1になる。

学習ノートを読み込んでいます…