[ACCEPTED]-What is the context free grammar for the complement of the double word over 0,1?-computation-theory

Accepted answer
Score: 12

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

L1={w1w|w{0,1}*}, L0={w0w|w{0,1}*}.

These languages 13 can be defined with the following CFG:

S0/1 -> |0S0|1S1|0S1|1S0

Now 12 look at L3:


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


and this is exactly 2


This implies that CFG languages are not 1 closed under complement.

Score: 0

The previously provided answer is incorrect 9 as it doesn't cover all strings present 8 in complement of L for example 011,110,11001, etc. (Previous 7 answer caused me lose some precious marks, so 6 updating :) ) The following grammar can 5 instead be used to prove that L complement 4 is CFL.




A 3 generates words of odd length with a in 2 the centre. Same for B and b.

More clear 1 explanation is present here.

More Related questions