アルファベット {a, b} 上の言語のうち、正規言語でないものはどれか。

解説

正解は「$\{a^n{b}^n\mid n\geqq 0\}$」です。この言語を受理するには、読んだ a の個数を正確に覚えておき、同じ数の b と照合する必要があります。有限オートマトンの状態は有限個しかないため任意に大きな n を覚えられず、ポンピング補題によって正規言語でないことが示せます。スタックを使うプッシュダウンオートマトンなら受理でき、文脈自由言語に属します。「$\{a^m{b}^n\mid m,n\geqq 0\}$」は個数を照合する必要がなく、正規表現 a*b* で表せます。「a の個数が偶数である文字列全体」は偶奇の2状態で受理できます。「ab で終わる文字列全体」は正規表現 (a|b)*ab で表せます。