平成29年度 I-2-5

解説

この問題で問われていること

<数値列>::=01|0<数値列>1(::=は定義、|はOR)で表現できる数値列を選ぶ問題。

解き方

① <数値列>::=01|0<数値列>1 は、01 の外側を 0 と 1 で包んでいく → 01、0011、000111… と「0がn個の後に1がn個」
② 0が3個・1が3個で、0が先に並ぶのは 000111
③ ④

正解が正しい理由

定義は、<数値列>が「01」であるか、または「0の後に<数値列>を挟んで1が続く」ものであることを意味する。これを繰り返し適用すると、01、0011、000111、00001111…と、0がn個続いた後に1がn個続く形の文字列(n≧1)が得られる。選択肢の中で、この形(0が3個の後に1が3個)に当てはまるのは、000111である。したがって④が正しい。

各選択肢について

• ① 111110は、1が並んだ後に0が続く形で、0が先に来る定義に合わない。
• ② 111000は、1が3個の後に0が3個続く形で、0が先の定義に合わない。
• ③ 101010は、0と1が交互に並ぶ形で、0がn個の後に1がn個という形ではない。
• ④ 000111は、0が3個の後に1が3個続く形で、0<0<01>1>1と3回展開した形に一致する。これが正答。
• ⑤ 000001は、0が5個の後に1が1個で、0と1の個数が等しくないため、定義に合わない。

覚えるべきポイント

BNFの再帰的定義<数値列>::=01|0<数値列>1は、0^n1^n(n≧1)という「0と1が同数で、0が先に並ぶ」形の文字列を生成する。再帰の基底(01)と再帰の展開を1段ずつ適用して確かめるとよい。