context-free-grammar - 双字补码超过 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)(a)(x_2^m)(y_1^n)(b)(y_2^n)

这正是

(L1L2)U(L2L1)

这意味着 CFG 语言在补码下不是封闭的。

Answer 2

先前提供的答案是不正确的，因为它没有涵盖 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 相同。

这里有更清楚的解释。