Let $\Sigma = \left\{ 0,\,1,\,2\right\}$. I want to look at the following language: $L=\left\{ xyz \, | \, |x|_0 + |z|_0 = |x|_2 +|z|_2 \wedge y \in \left\{ 1 \right\} ^{*} \right\}$.
I would like to prove or disprove $L$ being context-free
I'm having a very hard time to construct a context-free grammer for $L$, so I attempted to build a non-deterministic PDA.
My attempt goes in the direction of: If i want to sum the zeroes from $x$ and $z$, and fron this sum to substract the sum of $2$s from both $x$ and $z$, I can do it differently:
I can count the number of $0$s from $x$ by inserting a #, then remove one # for every $2$ I count, if negative I'll push @ . Then I will do the same with $z$.
The points are:
- I'm not sure if this idea will work?
- If this language is CFL, I have no idea how to begin constructing a CFL grammer for it?