theory - 上下文无关语言问题（Pumping Lemma）

Question

我知道这与编程没有直接关系，但我想知道是否有人知道如何将泵引理应用于以下证明：

证明L={(a^n)(b^n)(c^m) : n!=m}不是上下文无关语言

我对应用抽水引理非常有信心，但这真的让我很恼火。你怎么看？

Answer 1

编辑：我完全把你带到了错误的轨道上。当我自己还没有完全解决问题时，当我试图提供帮助时，就会发生这种情况。

奥格登引理

假设 L 是上下文无关的。根据奥格登引理，存在一个整数 p，它具有以下性质：

给定 L 中至少 p 个符号长的字符串 w，其中至少有 p 个符号被“标记”，w 可以表示为 uvxyz，它满足：

1. x 至少有一个标记符号，
2. 要么 u 和 v 都有标记符号，要么 y 和 z 都有标记符号，
3. vxy 最多有 p 个标记符号，并且
4. uv ⁱ xy ⁱ z 在 L 中，因为 i >= 0

这就是奥格登引理。现在，让 q 是一个整数，它可以被不大于 p 的每个正整数整除。令 w = a ^p+q b ^p+q c ^p。标记每个 c。通过#2，u 或v 必须至少包含一个c。如果 u 或 v 包含任何其他符号，则 #4 失败，因此 u 和 v 必须仅包含 c。但是当 i = q/|uv| 时，#4 失败。我们知道 q 可以被 |uv| 整除 因为 p > |uv| > 0，并且 q 可以被所有小于 p 的正整数整除。

请注意，当您标记所有符号时，Ogden 引理变成了抽水引理。

抽引理

假设 L 是上下文无关的。根据抽水引理，有一个长度 p（不一定与上面的 p 相同），使得 L 中的任何字符串 w 都可以表示为 uvxyz，其中

1. |vxy| <= p,
2. |维| >= 1，并且
3. uv ⁱ xy ⁱ z 在 L 中，因为 i >= 0。

给定 L 中的字符串 w，m > n 或 m < n。假设 p = 2。

假设 m > n。（注意 Λ 表示空字符串。）

• 设 u = a ⁿ b ⁿ c ^m-1
• 让 v = c
• 令 x = Λ
• 设 y = Λ
• 令 z = Λ

假设 n > m。

• 设 u = ^n-1
• 令 v = a
• 令 x = Λ
• 让 y = b
• 令 z = b ^n-1 c ^m

这表明没有来自 L 的字符串提供使用泵引理来假设 L 是上下文无关语言（即使它是上下文敏感的）的反例。