生成規則 S → SS、S → (S)、S → ε（ε は空列）をもつ文法から導出できる記号列はどれか。

解説

正解は「(()())」です。この文法は、対応のとれた括弧の列を生成します。例えば S ⇒ (S) ⇒ (SS) ⇒ ((S)S) ⇒ (()S) ⇒ (()(S)) ⇒ (()()) と導出できます。どの規則も開き括弧と閉じ括弧を対で加えるので、生成される列は左右の括弧の数が等しく、先頭から数えたどの時点でも閉じ括弧の数が開き括弧の数を超えません。「())(」は3文字目までで閉じ括弧が開き括弧を上回るので導出できません。「(()」は開き括弧が多く、数が合いません。「)(」は先頭が閉じ括弧で、最初から条件に反します。括弧の対応の判定は、スタックを使うプッシュダウンオートマトンで行えます。