上下文无关语言的抽取引理解释

上下文无关语言 (CFL) 的抽取引理用于证明一个语言不是上下文无关语言。

假设 L 是上下文无关语言。

则存在一个抽取长度 n，使得任何长度大于等于 n 的字符串 w εL 可以写成如下形式：

|w|>=n

我们可以将 w 分成 5 个字符串，w=uvxyz，如下所示：

• |vxy| >=n
• |vy| ≠ ε
• 对于所有 k>=0，字符串 uv^kxy^kz∈L

下面解释了使用抽取引理证明语言不是上下文无关语言的步骤：

• 假设 L 是上下文无关语言。
• 抽取长度为 n。
• 所有长度大于 n 的字符串都可以被抽取 |w|>=n。
• 现在在 L 中找到一个字符串 'w'，使得 |w|>=n。
• 将 w 分成 uvxyz
• 证明对于某些 k，uv^kxy^kz ∉L
• 然后，考虑 w 可以分成 uvxyz 的方式。
• 证明这些方式中没有一个能够同时满足所有 3 个抽取条件。
• w 无法被抽取（矛盾）。

示例

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

解答

• 设 L 为上下文无关语言。
• L 必须满足抽取长度，例如 n。
• 现在我们可以取一个字符串，例如 s=xⁿyⁿzⁿ
• 我们将 s 分成 5 个字符串 uvxyz。

设 n=4，则 s=x⁴y⁴z⁴

情况 1

v 和 y 各自只包含一种类型的符号。

（我们只考虑 v 和 y，因为 v 和 y 的幂是 uv²xy²z）

X xx x yyyyz z zz

=uv^kxy^kz 当 k=2

=uv²xy²z

=xxxxxxyyyyzzzzz

=x⁶y⁴z⁵

（x 的数量 ≠ y 的数量 ≠ z 的数量）

因此，结果字符串不满足条件。

x⁶y⁴z⁵ ∉ L

如果一种情况失败，则无需检查其他条件。

情况 2

v 或 y 包含多种类型的符号。

Xx xx yy y y zzzz

=uv^kxy^kz (k=2)

=uv²xy²z

=xxxxyyxxyyyyyzzzz

=x⁴y²x²y⁵z²

这个字符串不符合我们字符串 xⁿyⁿzⁿ 的模式。

Bhanu Priya

更新于：2021年6月12日

31K+ 次浏览

开启您的职业生涯

通过完成课程获得认证

开始学习