让我们证明 L3 是我们正在寻找的语言。首先，正如我们所见，它处理所有可能的奇数长度单词。对于偶数长度的单词，如果在语言中，至少有一对终结符，并且单词的两侧不同。称这对为 a 和 b。每个偶数词都可以这样划分：
(x_1^m)(a)(x_2^m)(y_1^n)(b)(y_2^n)
这正是
(L1L2)U(L2L1)
这意味着 CFG 语言在补码下不是封闭的。
First of all observe the fact that any odd word is part of the language. Let's define the following languages:
L1={w1w|w{0,1}*}, L0={w0w|w{0,1}*}
These languages can be defined with the following CFG:
S0/1 -> |0S0|1S1|0S1|1S0
Now look at L3:
L3=(L1)U(L2)U(L1L2)U(L2L1)
It is context free from closure to union and concatenation.
Let's prove that L3 is the language we're looking for. First of all as we have seen it deals with all possible odd length words. As for the even length words, if they are in the language, there is one pair of terminals, at least, which is different on both sides of the word. Call this pair a and b. Every even word can be divided like this:
(x_1^m)(a)(x_2^m)(y_1^n)(b)(y_2^n)
and this is exactly
(L1L2)U(L2L1)
This implies that CFG languages are not closed under complement.
The previously provided answer is incorrect as it doesn't cover all strings present in complement of L for example 011,110,11001, etc. (Previous answer caused me lose some precious marks, so updating :) ) The following grammar can instead be used to prove that L complement is CFL.
S→A|B|AB|BA
A→a|aAa|aAb|bAb|bAa
B→b|aBa|aBb|bBb|bBa
A generates words of odd length with a in the centre. Same for B and b.
发布评论
评论（2）
首先，请注意以下事实：任何奇怪的单词都是语言的一部分。让我们定义以下语言：
这些语言可以使用以下 CFG 来定义：
现在看看 L3：
它是上下文无关的，从闭包到并集和串联。
让我们证明 L3 是我们正在寻找的语言。首先，正如我们所见，它处理所有可能的奇数长度单词。对于偶数长度的单词，如果在语言中，至少有一对终结符，并且单词的两侧不同。称这对为 a 和 b。每个偶数词都可以这样划分：
这正是
这意味着 CFG 语言在补码下不是封闭的。
First of all observe the fact that any odd word is part of the language. Let's define the following languages:
These languages can be defined with the following CFG:
Now look at L3:
It is context free from closure to union and concatenation.
Let's prove that L3 is the language we're looking for. First of all as we have seen it deals with all possible odd length words. As for the even length words, if they are in the language, there is one pair of terminals, at least, which is different on both sides of the word. Call this pair a and b. Every even word can be divided like this:
and this is exactly
This implies that CFG languages are not closed under complement.
之前提供的答案是不正确的，因为它没有涵盖 L 的补码中存在的所有字符串，例如 011,110,11001 等。（之前的答案导致我失去了一些宝贵的分数，所以更新:)）
下面的语法可以用来证明 L 补码是 CFL。
S→A|B|AB|BA
A→a|aAa|aAb|bAb|bAa
B→b|aBa|aBb|bBb|bBa
A 生成以 a 为中心的奇数长度的单词。 B 和 b 相同。
此处提供了更清晰的解释。
The previously provided answer is incorrect as it doesn't cover all strings present in complement of L for example 011,110,11001, etc. (Previous answer caused me lose some precious marks, so updating :) )
The following grammar can instead be used to prove that L complement is CFL.
S→A|B|AB|BA
A→a|aAa|aAb|bAb|bAa
B→b|aBa|aBb|bBb|bBa
A generates words of odd length with a in the centre. Same for B and b.
More clear explanation is present here.