CFG 的泵送引理

---

引理

如果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不是上下文无关语言。