对于0.1以上的双字补语，上下文无关文法是什么？

Question

什么是L = {ww | w属于{0,1} *}的补集的CFG？

Answer 1

首先观察一个事实，即任何奇怪的单词都是该语言的一部分。我们定义下列语言：

L1 = {w1w | w {0,1} *}，L0 = {w0w | w {0,1} *}。

这些语言可以用下面的CFG来定义：

S0/1 - > | 0S0 | 1S1 | 0S1 | 1S0

现在看看L3：

L3 =（L1）U （L2）U（L1L2）U（L2L1）

它是从关闭到联合和级联的上下文。
让我们证明L3是我们正在寻找的语言。首先，正如我们所看到的，它处理所有可能的奇数字。至于长度单词，如果它们在语言中，则至少有一对终端，这两个终端在单词的两侧是不同的。称这对a和b。每个偶数字可以被划分是这样的：

（X_1^M）（一）（X_2^M）（Y_1^N）（B）（Y_2^N）

而这正是

（L1L2）U（L2L1）

这意味着CFG语言不是在补运算下封闭。