上下文无关文法抽取引理

引理

如果L是一个上下文无关语言，则存在一个抽取长度p，使得任何长度≥ p的字符串w ∈ L可以写成w = uvxyz，其中vy ≠ ε，|vxy| ≤ p，并且对于所有i ≥ 0, uvⁱxyⁱz ∈ L。

抽取引理的应用

抽取引理用于检查文法是否为上下文无关文法。让我们举个例子来说明如何检查。

问题

找出语言L = {xⁿyⁿzⁿ | n ≥ 1}是否是上下文无关语言。

解答

假设L是上下文无关的。那么，L必须满足抽取引理。

首先，选择抽取引理中的一个数n。然后，取 z 为 0ⁿ1ⁿ2ⁿ。

将z分解为uvwxy，其中

|vwx| ≤ n 且 vx ≠ ε。

因此，vwx不能同时包含 0 和 2，因为最后一个 0 和第一个 2 之间的距离至少为 (n+1) 个位置。有两种情况：

情况 1 - vwx 没有 2。则vx只包含 0 和 1。则uwy（它必须属于L）有n个 2，但少于n个 0 或 1。

情况 2 - vwx 没有 0。

这里出现了矛盾。

因此，L不是上下文无关语言。