string - 使用 Ogden’s Lemma 与常规 Pumping Lemma 进行上下文无关语法

Question

我正在学习问题中引理之间的区别。我能找到的每个引用资料都使用以下示例:

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

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

选择 w = uvxyz, s.t. |维| > 0, |vxy| <= p。
假设 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 的类似论据。然后就抽你想要的任何东西。)

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

谢谢!

Answer 1

这里一个重要的绊脚石问题是“能够泵送”并不意味着上下文无关，而是“不能泵送”表明它不是上下文无关的。同样，being grey does not imply you're an elephant, but being an elephant does imply you're grey...

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} 的草图证明不是上下文无关的(虽然它满足抽水引理，但不满足奥格登引理):

Pumping lemma for context free grammars:

If a language L is context-free, then there exists some integer p ≥ 1 such that any string s in L with |s| ≥ p (where p is a pumping length) can be written as s = uvxyz
with substrings u, v, x, y and z, such that:
1. |vxy| ≤ p,
2. |vy| ≥ 1, and
3. u v^n x y^n z is in L for every natural number n.

在我们的例子中:

对于任何 s在 L (与 |s|>=p) :

如 s包含 a s 然后选择 v=a, x=epsilon, y=epsilon (我们有 与上下文无关的语言没有矛盾 )。

如 s不包含 a s( w=b^j c^k d^l 和 j 、 k 或 l 之一非零，因为 |s|>=1 )然后选择 v=b (如果 j>0 , v=c elif k>0 , 否则 v=c ), x=epsilon , y=epsilon (我们有 与上下文无关的语言没有矛盾 )。

(很遗憾: 使用抽水引理我们无法证明有关 L 的任何事情!
注意:以上基本上是您在问题中给出的论点。)

Ogden's Lemma:

If a language L is context-free, then there exists some number p > 0 (where p may or may not be a pumping length) such that for any string w of length at least p in L and every way of "marking" p or more of the positions in w, w can be written as w = uxyzv
with strings u, x, y, z, and v such that:
1. xz has at least one marked position,
2. xyz has at most p marked positions, and
3. u x^n y z^n v is in L for every n ≥ 0.

注意:这个标记是奥格登引理的关键部分，它说:“不仅可以“抽取”每个元素，而且可以使用任何 p 标记位置抽取“。

在我们的例子中:

让 w = a b^p c^p d^p并标记 b 的位置s(其中有 p ，所以 w 满足奥格登引理的要求)，让 u,x,y,z,v是满足奥格登引理 ( z=uxyzv) 条件的分解。

如 x或 z包含多个符号，然后 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

在每种情况下(通过比较 b s、 c s 和 d s 的数量)我们可以看到 u x^2 v y^2 z不在 L (我们有 矛盾 (!) 与上下文无关的语言，即 我们已经证明 L 不是上下文无关的 )。

.

总结一下， L不是上下文无关的，但是这个 无法使用抽水引理进行演示 (但可以通过奥格登引理)，因此 we can say那:

Ogden's lemma is a second, stronger pumping lemma for context-free languages.