I have a problem with finding out if the complement of language L is context free.
$L = \{ ww : w \in \{a,b\}^{*} \wedge \text{ }w \text{ number of }a\text{'s in }w \equiv \text{number of }b\text{'s in }w \text{ (mod 3)} \}$
Is there any clever way to answer this question? I have no idea how to deal easily with this modulo 3 requirement . I would be grateful for any help.
Ok. And what about proving it is context free if it is not equal in mod3?
The language is indeed context-free. Let $A = \{a,b\}$ and let $$ L_0 = \{ww \mid w \in A^*\} \quad \text{and} \quad L_1 = \{ w \mid |w|_a \equiv |w|_b \bmod 3\} $$ Then $L = L_0 \cap L_1$ and thus its complement $L^c$ is equal to $L_0^c \cup L_1^c$. Then $L_1$ is regular language, since $L_1 = f^{-1}(0)$ where $f$ is the monoid morphism from $A^*$ to $\mathbb{Z}/3\mathbb{Z}$ defined by $f(w) = |w|_a - |w|_b$. It follows that $L_1^c$ is regular and it suffices to show that $L_0^c$ is context-free. This is more difficult, but this question Show that $\{ xy \mid |x| = |y|, x \not= y \}$ is context-free already received an answer on Computer Science Stack Exchange.
EDIT. Here is an automaton for $L_1$. The set of states is $Q = \{0, 1, 2\}$, $0$ is the initial state and the unique final state. The transitions are $0 \xrightarrow{a} 1 \xrightarrow{a} 2 \xrightarrow{a} 0$ and $0 \xrightarrow{b} 2 \xrightarrow{b} 1 \xrightarrow{b} 0$.