生成規則 S → aSc、S → T、T → bT、T → ε（ε は空列）をもち、開始記号が S である文法が生成する言語はどれか。

解説

正解は「$\{a^n{b}^m{c}^n\mid m,n\geqq 0\}$」です。S → aSc を n 回適用すると $a^{n}S{c}^n$ となり、外側の a と c の個数が等しくなります。次に S → T で T に移り、T → bT を m 回、T → ε を1回適用すると、内側に b が m 個並びます。b の個数は a, c の個数と無関係に決められます。「$\{a^n{b}^n{c}^n\mid n\geqq 0\}$」は3種類の個数がすべて等しい言語で、文脈自由文法では生成できないことが知られています。「$\{a^m{b}^n{c}^k\mid m,n,k\geqq 0\}$」は、a と c の個数が等しいという制約を見落としています。「$\{a^n{c}^n{b}^m\mid m,n\geqq 0\}$」は b の位置が誤っています。