7

我正在学习问题中词条之间的区别。我能找到的每个参考都使用了这个例子：

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

以显示两者之间的区别。我可以找到一个使用常规引理来“反驳”它的例子。

选择 w = uvxyz, st |vy| > 0, |vxy| <= 页。假设 w 包含相等数量的 b、c、d。

我选择了：

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

抽 y 只会增加 a 的数量，如果 |b|=|c|=|d| 起初，它现在仍然会。

（如果 w 没有 a 的类似论点。然后随便抽你想要的。）

我的问题是，奥格登引理如何改变这种策略？“标记”有什么作用？

谢谢！

4

2 回答 2

15

这里一个重要的绊脚石是“能够抽水”并不意味着无上下文，而“不能抽水”表明它不是无上下文的。同样，灰色并不意味着你是一头大象，但作为一头大象确实意味着你是灰色的......

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，使得withs中的任何字符串（其中是泵送长度）都可以写成 带有 substrings ，这样： 1. 、 2.和 3.是每个自然的号。L|s| ≥ pps = uvxyz
u, v, x, y and z
|vxy| ≤ p
|vy| ≥ 1
u v^n x y^n zLn

在我们的示例中：

对于任何sin L(with |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（如果j>0，v=celif k>0，else v=c），，x=epsilon（y=epsilon 我们与上下文无关的语言没有矛盾） 。

（所以不幸的是：使用抽水引理我们无法证明任何事情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满足奥格登引理的要求），令u,x,y,z,v是满足奥格登引理条件的分解 ( z=uxyzv)。

  • 如果xorz包含多个符号，u x^2 y z^2 w则不在 中L，因为会有符号顺序错误（考虑(bc)^2 = bcbc）。
  • 要么 要么x必须z包含b（根据引理条件 1。）

这给我们留下了五个需要检查的情况（对于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它不是上下文无关的，但这不能使用 The Pumping Lemma 来证明（但可以通过 Ogden 的引理），因此我们可以说：

Ogden 引理是上下文无关语言的第二个更强大的引理。

于 2012-10-15T01:37:10.390 回答
0

我不太确定如何在这里使用奥格登引理，但你的“证明”是错误的。当使用泵引理来证明一种语言不是上下文无关的时，您不能选择拆分为 uvxyz。拆分是“为您”选择的，您必须证明任何 uvxyz 都不满足引理。

于 2012-10-10T02:51:19.830 回答