1. 证明一个语言不是上下文无关的¶
1.1. 引言¶
我们现在有了大量证据表明存在不属于上下文无关语言类的语言。因此，就像我们已经有方法可以证明一个语言是否为正则语言一样，我们现在希望找到方法来证明一个语言是否为上下文无关语言。当我们研究正则语言时，我们开发了两种工具来帮助我们判断一个语言是否为正则语言。其中一种是正则语言的封闭性质。如果正确使用它们，它们既能帮助我们证明语言是正则的，也能帮助我们证明它们不是正则的。特别是，我们可以通过对已知正则语言应用封闭性质来生成该语言，从而证明该语言是正则的。此外，我们可以通过对已知正则语言应用已知封闭性质来操作它，从而生成一个已知非正则语言，以此证明该语言不是正则的。
以类似的方式，上下文无关文法存在闭包性质。因此，我们可以利用这些性质，在适当的情况下证明某种语言是上下文无关文法，同时也证明其他语言不是上下文无关文法。
我们使用正则语言的泵引理来证明某些语言不是正则语言（因为我们能够证明它们不能被泵化）。同样，我们将看到存在上下文自由语言的泵引理（尽管它与正则语言的泵引理有些不同），并且这个上下文自由语言的泵引理可用于证明某些语言不是上下文自由语言。
1.2. 上下文无关语言的封闭性质¶
1.3. 上下文无关语言的泵引理¶
例如，考虑语言 \(L = a^nb^n\) 。对于任何 \(m\) ，字符串 \(a^mb^m\) 可以分解为 \(u = a^{m-1}\) 、 \(v = a\) 、 \(x = \lambda\) 、 \(x = b\) 和 \(z = b^{m-1}\) 。显然，字符串中的最后一个 \(a\) 和第一个 \(b\) 可以泵送任意次数，且每次泵送的数量相同。在推入机方面，这意味着可以将任意数量的 \(a\) 推入栈中，然后匹配相同数量的 \(b\) 。
1.4. 使用上下文无关文法泵引理证明一个语言不是上下文无关语言：示例 1¶
我们利用正则语言的泵引理证明一个语言不是正则的，方法是证明它不满足泵引理。
泵引理意味着上下文无关语言可以包含必须协调其两个部分行为的字符串。这是上下文无关文法产生式中的常见惯用语（例如 \(S \rightarrow aSb\) ），它符合先加载栈然后再卸载栈的概念。但与此同时，我们可以从泵引理的表述中看到，要求协调三个部分是不可能的。因此， \(L = \{a^nb^nc^n : n \ge 1\}\) 不是上下文无关语言这一结论并不令人惊讶。这种直觉在我们对上下文无关语言泵引理证明的第一个例子中得到了形式化阐述。
