CFG for $L = \{{ ABC \ | \ A, B, C \in \{{0,1\}}^∗ \ ,\ |A| = |B| = |C| \ \ and \ \ A\neq C\}}$ I need to find a CFG for $L = \{{ ABC \ | \ A, B, C \in \{{0,1\}}^∗ \ ,\ |A| = |B| = |C| \ \ and \ \ A\neq C\}}$ but after a lot of attempts I have failed miserably. Could I get some directions?
 A: Let $\square$ be the notation for a position where there is any symbol from the alphabet, so any letter in $\{0,1\}$.
We are looking for strings for which a certain position in first third $A$ such that the letter at the same position in $C$ differs. If this position in $A$ and $C$ has $x$ positions before, and $y$ positions after, we are looking for strings of the form $\underbrace{\square^x 0 \square^y}_A\underbrace{\square^{x+y+1}}_B\underbrace{\square^x 1 \square^y}_C$ (or with $0$ and $1$ swapped).
Looking it in this way, written in the order $x,y,x,y,x,y$ we cannot generate these strings, if we could we would be able to do $\{ a^n b^nc^n\min n\ge 1\}$ by just relabelling segments $A,B,C$. We can however, generate stings of the form $\square^x 0 \square^{2x+1} \square^{2y} 1 \square^y$. Which solves the problem.
This is the same approach as the language where the two halves differ: $\{AB\mid A,B\in\{0,1\}^*, |A|=|B|, A\neq B\}$. A very related construction was given here: Understanding the context free grammar of the following language
