使用Ogden引理与常规泵浦引理用于无上下文语法

Question

我正在学习问题中的引理之间的区别.我能找到的每个引用都使用了这个例子:

{(a^i)(b^j)(c^k)(d^l) : i = 0 or j = k = l}

显示两者之间的差异.我可以找到一个使用常规引理来"反驳"它的例子.

选择w = uvxyz,st | vy | > 0,| vxy | <= p.假设w包含相等数量的b,c,d's.

我选择了:

u,v,x = ?
y = (the string of a's)
z = (the rest of the string w)

抽取y只会增加a的数量,如果| b | = | c | = | d | 起初,它现在还会.

(类似的论据,如果w没有a.那么只需抽出你想要的任何东西.)

我的问题是,奥格登的引理如何改变这一策略？"标记"有什么作用？

谢谢!

Answer 1

这里一个重要的绊脚石问题是"能够泵送"并不意味着没有上下文,而是"无法泵送"表明它不是无环境的.同样,灰色并不意味着你是一头大象,但作为大象确实意味着你是灰色的......

Grammar context free        => Pumping Lemma is definitely satisfied  
Grammar not context free    => Pumping Lemma *may* be satisfied
Pumping Lemma satisfied     => Grammar *may* be context free
Pumping Lemma not satisfied => Grammar definitely not context free
# (we can write exactly the same for Ogden's Lemma)
# Here "=>" should be read as implies

也就是说,为了证明语言不是上下文,我们必须证明它失败(!)以满足这些语法中的一个.(即使它满足两者,我们还没有证明它是无上下文的.)

下面是一个L = { a^i b^j c^k d^l where i = 0 or j = k = l}没有上下文的草图证明(虽然它满足抽水引理,它不满足奥格登的引理):

无上下文语法的抽取引理:

如果语言L是上下文无关,则存在一些整数p ? 1,使得任何字符串s在L与|s| ? p(其中p是泵送长度)可被写为 s = uvxyz
与子串u, v, x, y and z,使得:
1 |vxy| ? p,
2 |vy| ? 1,和
3 u v^n x y^n z是在L为每一个自然号码n.

在我们的例子中:

对于任何s人L(有|s|>=p):

• 如果s包含as则选择v=a, x=epsilon, y=epsilon (并且我们与没有上下文的语言没有矛盾).
• 如果不s包含as(w=b^j c^k d^l以及之一j,k或者l非零,|s|>=1那么)则选择v=b(if j>0,v=celif k>0,else v=c)x=epsilon,y=epsilon (并且我们与无上下文的语言没有矛盾).

(所以不幸的是:使用Pumping Lemma我们无法证明任何事情L!
注意:上面的内容基本上就是你在问题中提出的论点.)

奥格登的引理:

如果一种语言L是无上下文的,那么存在一些数字p > 0(其中p可能是或可能不是抽水长度),使得对于任何w长度的字符串,至少p在L每个"标记" p或更多的位置中w,w可以是写为 w = uxyzv
与字符串u, x, y, z,和v使得:
1. xz具有至少一个经标记的位置,
2. xyz已至多p标记位置,和
3 u x^n y z^n v是在L为每一个n ? 0.

注意:这个标记是奥格登引理的关键部分,它说:"不仅每个元素都可以"抽",而且可以使用任何p标记位置进行抽吸".

在我们的例子中:

设置w = a b^p c^p d^p并标记bs 的位置(其中有p,w满足Ogden引理的要求),并让它u,x,y,z,v成为满足Ogden引理(z=uxyzv)条件的分解.

• 如果x或z包含多个符号,u x^2 y z^2 w则不存在L,因为将存在错误顺序的符号(考虑(bc)^2 = bcbc).
• 任一x或z必须包含b(由引理条件1)

这让我们有五个案例要检查(for i,j>0):

• x=epsilon, z=b^i
• x=a, z=b^i
• x=b^i, z=c^j
• x=b^i, z=d^j
• x=b^i, z=epsilon

在每种情况下(通过比较bs,cs和ds的数量)我们可以看到u x^2 v y^2 z不存在L (并且我们对语言的矛盾(!)是无上下文的,也就是说,我们已经证明这L不是上下文免费).

.

总而言之,L不是没有上下文的,但这不能使用抽取引理(但可以通过Ogden的引理)来证明,因此我们可以这样说:

Ogden的引理是无背景语言的第二个更强大的引理.