string - 使用Ogden的引理与常规抽引法进行上下文无关文法

我正在学习问题中引词之间的区别。我可以找到的每个参考都使用示例：{(a^i)(b^j)(c^k)(d^l) : i = 0 or j = k = l}以显示两者之间的差异。我可以找到一个使用常规引理“反证”它的示例。选择w = uvxyz，s.t. | vy | > 0，| vxy | 假设w包含相等数量的b，c，d。我选择了：u,v,x = εy = (the string of a's)z = (the rest of the string w)如果| b | = | c | = | d |，则y只会增加a的个数。起初，现在仍然如此。（如果w不带a，则类似的论点。然后随便泵上你想要的任何东西。）我的问题是，奥格登的引理如何改变这一策略？ “标记”是做什么的？谢谢！ 最佳答案 这里一个重要的绊脚石是，“能够泵送”并不意味着上下文无关，而是“无法泵送”表明它不是上下文无关。同样，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 satisfiedGrammar not context free => Pumping Lemma *may* be satisfiedPumping Lemma satisfied => Grammar *may* be context freePumping 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，但不满足Ogden的Lemma）：Pumping lemma for context free grammars: 如果语言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包含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， elif v=c，否则为k>0），v=c，x=epsilon（并且与上下文无关的语言没有矛盾）。（因此很遗憾：使用Pumping Lemma，我们无法证明有关y=epsilon的任何信息！注意：以上本质上是您在问题中提供的参数。）Ogden's Lemma: 如果语言L是上下文无关的，则存在某个数字L（其中p > 0可能是也可能不是抽水长度），使得对于长度中至少p的任何字符串w cc>，并且“标记” p或L，p中的更多位置的每种方式都可以写成 w 用字符串w和w = uxyzv这样： 1. u, x, y, z,至少具有一个标记的位置， 2. v最多具有xz标记的位置，并且 3.每个xyz中的p位于u x^n y z^n v中。注意：此标记是Ogden Lemma的关键部分，它说：“不仅可以“抽取”每个元素，还可以使用任何L标记的位置抽取它”。在我们的示例中：设n ≥ 0并标记p的位置（其中有w = a b^p c^p d^p，因此b满足Ogden引理的要求），并且p是满足Ogden引理条件的分解（ w）。如果u,x,y,z,v或z=uxyzv包含多个符号，则x不在z中，因为会有错误顺序的符号（请考虑u x^2 y z^2 w）。L或(bc)^2 = bcbc必须包含x（根据引理条件1）。这使我们需要检查五种情况（对于z）：bi,j>0x=epsilon, z=b^ix=a, z=b^ix=b^i, z=c^j在每种情况下（通过比较x=b^i, z=d^j，x=b^i, z=epsilon s和b的数量），我们可以看到c不在d中（并且与所使用的语言存在矛盾（！）。上下文无关，也就是说，我们已经证明u x^2 v y^2 z不是上下文无关的）。。总而言之，L不是上下文无关的，但是不能使用The Pumping Lemma（但可以由Ogden's Lemma来证明），因此we can say不能证明这一点： 奥格登的引理是上下文无关语言的第二个更强大的引理。