文脈自由言語ではないことが知られている言語はどれか。

解説

正解は「$\{a^n{b}^n{c}^n\mid n\geqq 0\}$」です。プッシュダウンオートマトンは a の個数をスタックに積んで b と照合できますが、照合で取り出した後は、c と比べるための情報が残りません。文脈自由言語に対するポンピング補題を用いると、十分長い $a^n{b}^n{c}^n$ を分割して繰り返したとき、3種類の個数をそろえたままにできないことが示せます。この言語は文脈依存言語です。「$\{a^n{b}^n\mid n\geqq 0\}$」は S → aSb | ε で生成できます。「{a, b} 上の回文全体」は S → aSa | bSb | a | b | ε で生成できます。「$\{a^n{b}^{2n}\mid n\geqq 0\}$」は S → aSbb | ε で生成できます。