# Context-free grammar for complement of $\{ab \mid b=\mathrm{complement}(a)\}$

I want to construct a context-free grammar for $$L=\Sigma^*-\{ab \mid b=\mathrm{complement} (a) , a,b \in \{0, 1\}^*\}$$ and prove the correctness of answer. The complement of a string is obtained by switching $$0$$s and $$1$$s. For example, $$\mathrm{complement}(001) = 110$$.

I'm trying to decompose the language but I'm not sure about the different cases I should consider. For example, I know that $$L$$ contains all strings with odd length. But what else do I have to consider? Also, I can't make sure that the language of constructed grammar equals the given language, so a proof is needed.

## 1 Answer

As you have noticed, you can decompose between words of odd length and words of even length. Since the odd part is quite easy, I will focus on the even one, that is $$L = \{uv \mid u, v\in \{0,1\}^*\wedge u\neq \mathrm{complement}(v)\}$$.

Given $$u, v\in\{0,1\}^*, |u|=|v|$$, if we write $$u = u_1…u_k$$ and $$v = v_1…v_k$$, then $$uv \in L$$ if and only if $$k \geq 1$$ and $$\exists i \in [\![1,k]\!], u_i = v_i$$. In that case, we can write $$uv = wu_ixv_iy$$ where $$|w| = u_1…u_{i-1}$$ and $$y = v_{i+1}…v_k$$. We also have $$|x| = k-i + i -1= k-1$$, so $$x$$ can be written as $$x = zt$$ with $$|z| = i-1 = |w|$$ and $$|t| = k-i = |y|$$.

We will now write a grammar to generate these words. Let's define:

$$S\to AA\mid BB$$

$$A \to 0 \mid 0A0 \mid 0A1 \mid 1A0 \mid 1A1$$

$$B\to 1\mid 0B0\mid 0B1 \mid 1B0 \mid 1B1$$

It is clear that $$A$$ rules will generate a word $$w0x$$ with $$|w| = |x|$$. That means that $$AA$$ will generate $$w0zt0y$$, with $$|w| = |z|$$ and $$|t| = |y|$$. The same thing can be done with $$BB$$.

(This answer was greatly inspired by this one.)