补集L'={ww|w属于{0,1}*}的CFG是什么?
补集L'={ww|w属于{0,1}*}的CFG是什么?
L1={w1w|w{0,1}*}, L0={w0w|w{0,1}*}
S0/1 -> |0S0|1S1|0S1|1S0
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)