上下文无关语言

上下文无关语言是可以用上下文无关文法定义的形式语言。所有上下文无关语言的集合同一于下推自动机所接受的语言的集合。

一个原型上下文无关语言是 ${\displaystyle L=\{a^n{b}^n:n\ge <!--\; \ge \; -->1\}}$ 和 是上下文无关语言而 是正则语言，下列语言也是上下文无关语言：

上下文无关语言不闭合于补集，交集或差集下。

上下文无关语言不闭合于交集下。其证明在 Sipser 97 中被作为习题给出。选用语言 ${\displaystyle A=\{a^m{b}^n{c}^n\mid <!--\; \mid \; -->m,n\ge <!--\; \ge \; -->0\}}$ 和 ${\displaystyle B=\{a^n{b}^n{c}^m\mid <!--\; \mid \; -->m,n\ge <!--\; \ge \; -->0\}}$，它们都是上下文无关的。它们的交集是 ${\displaystyle A\cap <!--\; \cap \; -->B=\{a^n{b}^n{c}^n\mid <!--\; \mid \; -->n\ge <!--\; \ge \; -->0\}}$，它可以用上下文无关语言的泵引理证实为非上下文无关的。

上下文无关语言的下列问题是不可判定的：

上下文无关语言的下列问题是可判定的：