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