使用Ogden的引理与常规抽引法进行上下文无关文法 [英] Using Ogden’s Lemma versus regular Pumping Lemma for Context-Free Grammars

问题描述

我正在学习问题中引词之间的区别.我可以找到的每个参考都使用示例:

I'm learning the difference between the lemmata in the question. Every reference I can find uses the example:

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

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

to show the difference between the two. I can find an example using the regular lemma to "disprove" it.

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

Select w = uvxyz, s.t. |vy| > 0, |vxy| <= p. Suppose w contains an equal number of b's, c's, d's.

我选择了:

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

如果| b | = | c | = | d |，则将y加到a的个数上.起初，现在仍然如此.

Pumping y will just add to the number of a's, and if |b|=|c|=|d| at first, it still will now.

(关于w是否没有a的类似参数.然后随便抽你想要的任何东西.)

(Similar argument for if w has no a's. Then just pump whatever you want.)

我的问题是，奥格登的引理如何改变这一策略? 标记"是做什么的?

My question is, how does Ogden's lemma change this strategy? What does "marking" do?

谢谢！

推荐答案

这里的一个重要绊脚石是，能够泵送"并不意味着上下文无关，而是不能泵抽"表明它不是上下文无关. . 类似地，变成灰色并非暗示您是大象，但是大象确实暗示您是灰色的...

One important stumbling issue here is that "being able to pump" does not imply context free, rather "not being able to pump" shows it is not context free. Similarly, 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

这就是说，为了证明一种语言不是不是上下文无关的，我们必须将其显示为失败(！)，以满足其中的一种引词. (即使这两个条件都满足，我们还没有证明它是上下文无关的.)

That is to say, in order to demonstrate that a language is not context free we must show it fails(!) to satisfy one of these lemmata. (Even if it satisfies both we haven't proved it is context free.)

以下是L = { a^i b^j c^k d^l where i = 0 or j = k = l}不是上下文无关的的草图证明(尽管它满足Pumping Lemma，但不满足Ogden的Lemma):

Below is a sketch proof that L = { a^i b^j c^k d^l where i = 0 or j = k = l} is not context free (although it satisfies The Pumping Lemma, it doesn't satisfy Ogden's Lemma):

如果语言L是上下文无关的，则存在一些整数p ≥ 1，因此可以写入L中带有|s| ≥ p的任何字符串s(其中p是抽水长度)作为 s = uvxyz
带有子字符串u, v, x, y and z，例如:
1. |vxy| ≤ p，
2. |vy| ≥ 1和
3.对于每个自然数n，u v^n x y^n z在L中.

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.

在我们的示例中:

对于L中的任何s(带有|s|>=p):

In our example:

For any s in L (with |s|>=p):

• 如果s包含a，则选择v=a, x=epsilon, y=epsilon (对于与上下文无关的语言，我们没有矛盾).
• 如果s不包含任何a(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 (并且与语言无关的语言我们没有强烈的矛盾).

• If s contains as then choose v=a, x=epsilon, y=epsilon (and we have no contradiction to the language being context-free).
• If s contains no as (w=b^j c^k d^l and one of j, k or l is non-zero, since |s|>=1) then choose v=b (if j>0, v=c elif k>0, else v=c), x=epsilon, y=epsilon (and we have no contradiction to the language being context-free).

(很遗憾:使用抽水引力，我们无法证明有关L的任何信息！
注意:以上内容实质上就是您在问题中提供的论据.)

(So unfortunately: using the Pumping Lemma we are unable to prove anything about L!
Note: the above was essentially the argument you gave in the question.)

如果语言L是上下文无关的，则存在某个数字p > 0(其中p可能是也可能不是抽水长度)，使得对于任何长度w的字符串，至少为L中的>以及标记" p或w，w中更多位置的每种方式都可以写成 w = uxyzv
带有字符串u, x, y, z,和v的字符串，例如:
1. xz至少具有一个标记的位置，
2. xyz最多具有p标记的位置，并且
3.每个n ≥ 0中的L中都包含u x^n y z^n v.

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.

注意:此标记是Ogden引理的关键部分，它说:不仅可以抽取"每个元素，还可以使用任何p标记的位置抽取它."

Note: this marking is the key part of Ogden's Lemma, it says: "not only can every element be "pumped", but it can be pumped using any p marked positions".

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

Let w = a b^p c^p d^p and mark the positions of the bs (of which there are p, so w satisfies the requirements of Ogden's Lemma), and let u,x,y,z,v be a decomposition satisfying the conditions from Ogden's lemma (z=uxyzv).

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

• If x or z contain multiple symbols, then u x^2 y z^2 w is not in L, because there will be symbols in the wrong order (consider (bc)^2 = bcbc).
• Either x or z must contain a b (by Lemma condition 1.)

这使我们有五个案例要检查(对于i,j>0):

This leaves us with five cases to check (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

• 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并非上下文无关).

in every case (by comparing the number of bs, cs and ds) we can see that u x^2 v y^2 z is not in L (and we have a contradiction (!) to the language being context-free, that is, we've proved that L is not context free).

.

总而言之，L不是上下文无关的，但这不能使用The Pumping Lemma (但由Ogden's Lemma的 can )进行证明，因此我们可以说:

To summarise, L is not context-free, but this cannot be demonstrated using The Pumping Lemma (but can by Ogden's Lemma) and thus we can say that:

奥格登的引理是针对上下文无关语言的第二次更强引理.

这篇关于使用Ogden的引理与常规抽引法进行上下文无关文法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！