我有语言：L = {0^i 1^i | 我 >= 0}
描述它的语法证明它是一种上下文无关语言：S -> 0S1 | e
如果一种语言是上下文无关的，Pumping Lemma 应该成立。然而，我无法让它工作，无论我选择“泵”什么，我都会得到 0 和 1 的混合，例如 0101。
我是否正确地说它真的是一种上下文无关的语言？如果是这样，你能举一个使用 Pumping Lemma 的例子吗？
问问题
692 次
1 回答
0
如果您可以使用上下文无关语法来描述一种语言，那么该语言就是上下文无关的。使用抽水引理很难证明一种语言是上下文无关的，因为即使你找到一个可以抽水的字符串，仍然可能有一个不能抽水的字符串。
您通常使用抽水引理来证明一种语言不是上下文无关的。因为您所需要的只是一个无法抽出的字符串示例。
这是 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 中
于 2013-11-18T06:12:41.503 回答