什么是双字节0,1补集的无上下文文法？

Question

什么是双字节0,1补集的无上下文文法？

context-free-grammarcomputation-theory

3

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

- Uri

2

请原谅我持怀疑态度，但我有这样的印象，你想让我们替你完成作业。如果不是这种情况，请随意删除标签。 - phooji

5

@phooji：是的，这是作业。我认为早上五点是一个承认失败并寻求帮助的好时间。 - Uri

2

请在CSTheory上开始提出此类编程问题。 - Ravindra S

2

我投票关闭此问题，因为它与编程无关。这可能更适合[cs.se]。 - Tomerikoo

2个回答

0

先前提供的答案不正确，因为它没有涵盖补集中存在的所有字符串，例如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也是如此。更清晰的解释在这里。

- raaj

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Uri · Accepted Answer

首先观察到任何奇数单词都是语言的一部分。让我们定义以下语言：

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语言在补集运算下不封闭。