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语言不会在补充下关闭.