context-free-grammar - 使用抽引引理证明语法不是上下文无关的？

Question

我试图L={y#x|(y is a substring of x) ∧x,y∈{a,b}^* }使用抽水引理证明这不是上下文无关的，但我似乎无法做到这一点。如果

|vy|≠ε ,|vxy|≤k , uv^n xy^n z∈L ,∀n≥0

然后要么vxy两者兼有a，b要么只有，b要么只有a。

我怎样才能抽它来显示呢？

Answer 1

我同意 cHao 的观点，使用泵引理来表明一种语言不是上下文无关的。为了证明一种语言是上下文无关的，构建一个上下文无关语法或 DFA。

{y#x | y是x} 在字母表上的一个子集{a, b}*似乎不是上下文无关的，只是快速浏览一下。

让s = (a|b)^p#(a|b)^(2p)这是一个字符串，其中p字符之前#和2p之后的字符使其成为一个简单的子集。

我们现在需要将此字符串分解为x y^i zwhere|y| > 0和|xy| = p. 所以y必须由 之前的任何字符串组成#。我们现在可以将这个字符串“拉高”到第一个字符串之前的第一个字符串#大于第二个字符串。这不再是下半场的一个子集。这是一个矛盾，所以这种语言不是上下文无关的。