上下文无关语言问题(泵引理)
-
25-09-2019 - |
题
我知道这与编程没有直接关系,但我想知道是否有人知道如何将泵引理应用于以下证明:
显示 L={(a^n)(b^n)(c^m) :n!=m} 不是上下文无关的语言
我对应用泵送引理非常有信心,但这一点真的让我很恼火。你怎么认为?
解决方案
编辑:我完全把你引向了错误的道路。当我自己没有完全解决问题而试图提供帮助时,就会发生这种情况。
奥格登引理
假设 L 是上下文无关的。根据奥格登引理,存在一个具有以下性质的整数 p:
给定 L 中至少有 p 个符号长的字符串 w,其中至少有 p 个符号被“标记”,w 可以表示为 uvxyz,满足:
- x 至少有一个标记符号,
- u 和 v 都有标记符号,或者 y 和 z 都有标记符号,
- vxy 至多有 p 个标记符号,并且
- 紫外线我 坐标我 当 i >= 0 时,z 位于 L 中
这就是奥格登引理。现在,令 q 为可被每个不大于 p 的正整数整除的整数。令 w = ap+q 乙p+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,
- 紫外线我 坐标我 当 i >= 0 时,z 位于 L 中。
给定 L 中的字符串 w,m > n 或 m < n。假设 p = 2。
假设 m > n。(请注意,Λ 表示空字符串。)
- 设 u = an 乙n C米-1
- 令 v = c
- 设 x = Λ
- 设 y = Λ
- 令 z = Λ
假设 n > m。
- 设 u = an-1
- 令 v = a
- 设 x = Λ
- 令 y = b
- 令 z = bn-1 C米
这表明 L 中的任何字符串都没有提供使用泵引理来假设 L 是上下文无关语言(即使它是上下文敏感的)的反例。
不隶属于 StackOverflow