0
$\begingroup$

I am studying push down automata.

When I read a solution for showing $L = \{x\#y \mid x \neq y, x,y \in \{0,1\}^*\}$ is a CFL, I could understand $L = L_1 \cup L_2$, $L_1 = \{x\#y\mid|x| \neq |y|\}$, $L_2 = \{x\#y \mid|x| = |y|,x \neq y\}$, and make a CFG for $L_1$, but I don't know how to make a CFG for $L_2$, since $y$ is not a reverse string of $x$. How can I know the $i_\text{th}$ symbol is different?

Note this question is different from Show that { xy ∣ |x| = |y|, x ≠ y } is context-free since we have an additional separator $\#$.

$\endgroup$