# Finding a grammar for $L = \{ 0^x1^y0^z1^w | x+w=y+z\}$

I have found an exercise where it tasks to provide a grammar and a pushdown automata for $$L = \{ 0^x1^y0^z1^w | x+w=y+z\}$$

While finding a pushdown automata for it is quite easy (four states and two stack symbols $$p$$ and $$t$$, where $$0^x$$'s push $$p$$, $$1^t$$'s and $$0^z$$'s pop $$p$$ or push $$t$$ if there are no $$p$$'s, and $$1^w$$'s pop $$t$$), I am unable to find an equivalent grammar for it. Perhaps there is some trick for this?

Let's write the condition $$x+w=y+z$$ in a different way: $$x-y=z-w$$. We consider two cases: $$x \geq y$$ and $$y \geq x$$. If $$x \geq y$$, let $$x = y+a$$. Then we are interested in words of the form $$0^{y+a} 1^y 0^{w+a} 1^w = 0^a 0^y 1^y 0^a 0^w 1^w.$$ If $$y \geq x$$, let $$y=x+b$$. Then we are interested in words of the form $$0^x 1^{x+b} 0^z 1^{z+b} = 0^x 1^x 1^b 0^z 1^z 1^b.$$ We can generate words of the first form using the grammar \begin{align} &T_1 \to AW \\ &A \to 0A0 \mid Y \\ &Y \to 0Y1 \mid \epsilon \\ &W \to 0W1 \mid \epsilon \end{align} We can generate words of the second form using the grammar \begin{align} &T_2 \to XB \\ &X \to 0X1 \mid \epsilon \\ &B \to 1B1 \mid Z \\ &Z \to 0Z1 \mid \epsilon \end{align} Taking these two grammars together and adding a new rule $$S \to T_1 \mid T_2$$, we get a grammar for your language. Note that you can merge $$X,Y,Z,W$$. The resulting grammar is \begin{align} &S \to AX \mid XB \\ &A \to 0A0 \mid X \\ &B \to 1B1 \mid X \\ &X \to 0X1 \mid \epsilon \end{align}

I don't know if $$x$$, $$y$$, etc. can be $$0$$, so maybe there's something to fix (e.g., you'll need $$S\rightarrow \varepsilon$$ etc.), but you can try something like this:

$$S\rightarrow 0S1 \mid 0A0 \mid 1B1$$
$$A \rightarrow 0A0 \mid 1C0$$
$$B \rightarrow 1B1 \mid 1C0$$
$$C \rightarrow 1C0 \mid \varepsilon$$

Suppose $$w\geq x$$, then the idea is first generating the string $$0^x S' 1^x$$, then adding $$w-x$$ $$1$$'s on the right of the first $$0$$'s and the same number of $$0$$'s on the left of the last $$1$$'s, and so on; the case $$x\geq w$$ is similar.