what is the complement of the language L={ww : w ∈{a,b}* }

Question

The given language is not CFL ,it is CSL and CFL is not closed under complement operation ,Now I am not getting how to find it's complement ,please tell the approach .

Answer 1

Let $L'$ be the complement, $L'=\{a,b\}^*\setminus L$. Clearly every word in $L$ has even length, so every word of $\{a,b\}^*$ with odd length must be in $L_1$. Let

$$R=\left\{w\in\{a,b\}^*:|w|\text{ is odd}\right\}\;;$$

then $R\subseteq L_1$.

It remains to determine what word of even length are in $L_1$. These are precisely the words in $\{a,b\}^*$ that can be written in the form $uv$, where $u\ne v$ and $|u|=|v|$. Thus

$$L_1=R\cup\left\{uv\in\{a,b\}^*:u\ne v\text{ and }|u|=|v|\right\}\;.$$