在0.1之上的双字补码的上下文无关文法是什么？ [英] What is the context free grammar for the complement of the double word over 0,1?

问题描述

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

What is the CFG of the complement of L={ww|w belongs to {0,1}*}?

推荐答案

<首先，请注意以下事实：任何奇数词都是语言的一部分。让我们定义以下语言：

First of all observe the fact that any odd word is part of the language. Let's define the following languages:

可以使用以下CFG定义这些语言：

These languages can be defined with the following CFG:

现在看L3：

Now look at L3:

从上下文到闭包，并集和串联都不受上下文限制。


让我们证明L3是我们想要的语言。首先，正如我们所看到的，它处理所有可能的奇数长度的单词。至于偶数长度的单词，如果使用语言，则至少有一对终端，单词的两边都不同。将此对称为a和b。每个偶数单词都可以这样划分：

It is context free from closure to union and concatenation.
Let's prove that L3 is the language we're looking for. First of all as we have seen it deals with all possible odd length words. As for the even length words, if they are in the language, there is one pair of terminals, at least, which is different on both sides of the word. Call this pair a and b. Every even word can be divided like this:

，这恰好是

and this is exactly

这表示CFG语言未按补码封闭。

This implies that CFG languages are not closed under complement.

这篇关于在0.1之上的双字补码的上下文无关文法是什么？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！