我知道这与编程没有直接关系,但我想知道是否有人知道如何将泵引理应用于以下证明:
Show that L={(a^n)(b^n)(c^m) : n!=m} is not a context free language
我对应用泵引理非常有信心,但是这个真的让我很恼火。你觉得怎么样?
最佳答案
编辑:我完全把你引入了错误的轨道。这就是当我自己没有完全解决问题而尝试提供帮助时会发生的情况。
奥格登引理
假设 L 是上下文无关的。根据奥格登引理,存在一个具有以下性质的整数 p:
给定 L 中至少有 p 个符号长的字符串 w,其中至少有 p 个符号被“标记”,w 可以表示为 uvxyz,满足:
- x 至少有一个标记符号,
- u 和 v 都有标记符号,或者 y 和 z 都有标记符号,
- vxy 最多有 p 个标记符号,并且
- u vi x yi z 在 L 中,i >= 0
这就是奥格登引理。现在,令 q 为可被每个不大于 p 的正整数整除的整数。设 w = ap+q bp+q cp。标记每个 c。根据#2,u 或v 必须至少包含一个c。如果 u 或 v 包含任何其他符号,则 #4 失败,因此 u 和 v 必须仅包含 c。但是当 i = q/|uv| 时#4 失败。我们知道 q 可以被 |uv| 整除因为 p > |uv| > 0,并且 q 可被所有小于 p 的正整数整除。
请注意,当您标记所有符号时,奥格登引理会变成泵引理。
泵浦引理
假设 L 是上下文无关的。根据泵引理,有一个长度 p(不一定与上面的 p 相同),使得 L 中的任何字符串 w 都可以表示为 uvxyz,其中
- |vxy| <=p,
- |vy| >= 1,并且
- u vi x yi z 位于 L 中,且 i >= 0。
给定 L 中的字符串 w,m > n 或 m < n。假设 p = 2。
假设 m > n。 (请注意,Λ 表示空字符串。)
- 设 u = an bn cm-1
- 令 v = c
- 设 x = Λ
- 设 y = Λ
- 令 z = Λ
假设 n > m。
- 令 u = an-1
- 令 v = a
- 设 x = Λ
- 设 y = b
- 令 z = bn-1 cm
这表明 L 中的任何字符串都没有使用泵引理提供反例来假设 L 是上下文无关语言(即使它是上下文相关的)。
关于theory - 上下文无关语言问题(泵引理),我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/2597124/