生成規則 S → aSb、S → ε（ε は空列）をもつ文脈自由文法が生成する言語はどれか。

解説

正解は「$\{a^n{b}^n\mid n\geqq 0\}$」です。S → aSb を n 回適用すると $a^{n}S{b}^n$ となり、最後に S → ε を適用すると $a^n{b}^n$ が得られます。n=0 の場合は最初に S → ε を適用するので、空列も生成されます。このように左右に1つずつ記号を加える規則で、a と b の個数をそろえられるのが文脈自由文法の特徴です。「$\{a^m{b}^n\mid m,n\geqq 0\}$」は a と b の個数が独立な言語ですが、この文法では個数が必ず等しくなります。「$\{(ab{)}^n\mid n\geqq 0\}$」は ab の繰返しで、abab はこの文法から生成できません。「$\{a^n{b}^n\mid n\geqq 1\}$」は、空列を生成できることを見落としています。