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

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:

L3=(L1)U(L2)U(L1L2)U(L2L1)

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:

(x_1^m)(a)(x_2^m)(y_1^n)(b)(y_2^n)

and this is exactly 2

(L1L2)U(L2L1)

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.

S→A|B|AB|BA

A→a|aAa|aAb|bAb|bAa

B→b|aBa|aBb|bBb|bBa

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