BNFと構文図 想定問題 2

01 と 0＜列＞1 に，列をつなげる規則を足したBNFで，作れる列を判定する問題です。

「＜列＞＜列＞」があると，作った列を横につなげられます。0 を開きかっこ，1 を閉じかっこと読み，左から読んで途中で 1 が多くならないか確かめます。

ア：○。01 と 01 を「＜列＞＜列＞」でつなげて作れます。

イ：×。左から読むと「011」の時点で 1 が 2 個，0 が 1 個となり，1 が多くなります。01 のあとに「10」が残り，これはどの規則でも作れません。

ウ：○。0101（01 と 01 をつないだもの）を 0＜列＞1 で囲むと，0 0101 1 ＝ 001011 になります。

エ：×。0 と 1 は 3 個ずつですが，「011」の時点で 1 が多くなるので作れません。答えは ア ○，イ ×，ウ ○，エ ×

• ＜列＞::=01｜0＜列＞1｜＜列＞＜列＞ のように「＜列＞＜列＞」を足すと，作った列を横につなげられる。0 を開きかっこ，1 を閉じかっこと読むと，正しく対応したかっこの並びになる（テキスト・覚えること）
• 0 と 1 の個数が同じでも，途中で 1 が多くなる列（0110 など）は作れない（テキスト・ひっかけ）
• 「＜列＞＜列＞」がある定義は，左から読んで，途中で 1 の数が 0 の数より多くならず，最後に同じ数になれば作れる（テキスト・解き方）