上下文自由语言问题(抽取引理)

Question

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

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

我对使用抽吸引理非常有信心,但这个真的让我感到厌烦.你怎么看？

Answer 1

编辑:我完全引导你走错了轨道.当我自己没有完全解决问题的时候,当我试图帮忙的时候会发生这种情况.

奥格登的引理

假设L是无上下文的.根据Ogden的引理,存在一个具有以下属性的整数p:

给定L中的字符串w至少p个符号长,其中这些符号中的至少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. | VY | > = 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 = a ^n-1
• 设v = a
• 设x =Λ
• 设y = b
• 设z = b ^n-1 c ^m

这表明L的字符串没有提供使用抽取引理的反例,假设L是无上下文语言(即使它是上下文敏感的).