Context-free grammar for all words not of the form w#w

I was asked to define a CFG for the complement of $\{w\#w \mid w \in \{0,1\}^\}$ and I'm struggling to define it. I think it is quite similar to defining a CFG for the complement of $\{ww \mid w \in \{0,1\}^\}$, but I'm finding that the '#' really messes things up. Is the language even context-free?

If a word is not of the form $w\#w$ then one of the following must happen:

• It contains no $\#$.

• It contains more than one $\#$.

• It is of the form $x\#y$, where $x,y \in \{0,1\}^*$ and $x \neq y$, in which case one of the following must happen:

• $|x| > |y|$ or $|x|

• $x_i = 0$ and $y_i = 1$ for some $i$, or vice versa.

The only case which is non-trivial to handle is the last one, in which case we have a word of the form
$$
x_1 0 x_2 \# y_1 1 y_2,
$$
where $|x_1| = |y_1|$. We can split this into
$$
x_1 \;\; 0x_2\# \;\; y_1 \;\; 1y_2,
$$
where $|x_1| = |y_1|$. This should make it clear how to construct a CFG for such words.

Altogether, we obtain the following grammar:
\begin{align}
&S \to A \mid B \mid C \mid D \mid E \mid F \\
&A \to 0A \mid 1A \mid \epsilon \\
&B \to A\#B \mid A\#A\#A \\
&C \to A0G \mid A1G \\
&D \to G0A \mid G1A \\
&G \to 0G0 \mid 0G1 \mid 1G0 \mid 1G1 \mid \# \\
&E \to E_11A \\
&E_1 \to 0E_10 \mid 0E_11 \mid 1E_10 \mid 1E_11 \mid 0A\# \\
&F \to F_10A \\
&F_1 \to 0F_10 \mid 0F_11 \mid 1F_10 \mid 1F_11 \mid 1A\# \\
\end{align}

In this grammar:

• $A$ generates words without $\#$

• $B$ generates words with more than one $\#$

• $C$ generates words of the form $x\#y$ with $|x| > |y|$

• $D$ generates words of the form $x\#y$ with $|x|

• $E$ generates words of the form $x_10x_2\#y_11y_2$ with $|x_1|=|y_1|$

• $F$ generates words of the form $x_11x_2\#y_10y_2$ with $|x_1|=|y_1|$

• $G$ generates words of the form $x\#y$ with $|x| = |y|$

StackExchange Computer Science Q#133551, answer score: 4