Search code examples
context-free-grammarcomputation-theory

What is the context free grammar for the complement of the double word over 0,1?

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

Solution

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

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

    These languages can be defined with the following CFG:

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

    Now look at L3:

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

    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:

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

    and this is exactly

    (L1L2)U(L2L1)

    This implies that CFG languages are not closed under complement.