context-free-grammar - 以下语言上下文无关语法吗？

Question

对于 n>=0，给定的语法 (a^na^na^n) 上下文是否自由？我尝试使用抽引引理，结果是，不，它不是上下文无关的。

Answer 1

为了使抽水引理起作用，您需要证明，您可以找到一个词并“抽水”以打破 PL 的规则。

在这种情况下，您已经a^n a^n a^n并且想要将这些单词拆分为一个单词 uv^kw ，以便它仍然处于指定的语法中。

在这种情况下，它将不起作用！

要看到这一点，我们必须考虑几种情况：

1) u 至少为 1（因为根据 PL 的定义 v 不能为空），使 v 和 w 成为 a 的其余部分

2) u 的长度a^n为，v 的长度至少为 a^n，w 的长度为a^n

3) ...

想象一下，您有一个长度为 k 的模板，并将其放在 a^na^na^n 的每个可以想象的位置下，如下所示：

如果仅添加 1 n，则生成的单词将不再 in a^n a^n a^n，因此 PL 失败。语言a^n a^n a^nequalsa^n b^n c^n是失败 PL 的标准示例。

旁注：如果 PL 没有失败，您不能断定该语法是上下文无关的。PL 只在一个方向上起作用。