context-free-grammar - 上下文无关语言与否？我可以写语法但不能使用抽引引理

Question

我有语言：L = {0^i 1^i | 我 >= 0}

描述它的语法证明它是一种上下文无关语言：S -> 0S1 | e

如果一种语言是上下文无关的，Pumping Lemma 应该成立。然而，我无法让它工作，无论我选择“泵”什么，我都会得到 0 和 1 的混合，例如 0101。

我是否正确地说它真的是一种上下文无关的语言？如果是这样，你能举一个使用 Pumping Lemma 的例子吗？

Answer 1

如果您可以使用上下文无关语法来描述一种语言，那么该语言就是上下文无关的。使用抽水引理很难证明一种语言是上下文无关的，因为即使你找到一个可以抽水的字符串，仍然可能有一个不能抽水的字符串。

您通常使用抽水引理来证明一种语言不是上下文无关的。因为您所需要的只是一个无法抽出的字符串示例。

这是 L = {0^i 1^i | 中的字符串示例 i >= 0} 以及如何抽水。

字符串 w=01，可拆分如下：

u = empty   
v = 0  
x = empty  
y = 1   
z = empty

uv^ixy^iz 对于每个 i >= 0 都在 L 中