Is the language over the alphabet {0,1,2} consisting of equal number of substrings "01" and "10" context-free?

Question

This language looks very similar to the regular language over {0,1} where $|w|_{01} = |w|_{10}$, but clearly because we're adding the 2 in the alphabet, it makes it not regular. Is it context-free however? I assume it is, but I can't prove it. I tried making a CFG and a PDA generating or recognizing it and I keep getting stuck when considering the third alphabet symbol.

Answer 1

The third alphabet symbol is irrelevant.

Just push the number of times a "$0$" immediately follows "$1$" in your stack and pop whenever "$1$" immediately follows "$0$", or vice versa if your stack is empty. At the end check if the stack is empty.

Answer 2

Consider the following languages over the alphabet $\{*,\mathtt 0,\mathtt 1,\mathtt 2\}$:

• $L_1$: the languages of all strings where $*$ can only occur immediately between a $\mathtt 0$ or a $\mathtt 1$ (in either order), and where $\mathtt 0$ and $\mathtt 1$ never occur next to each other.

• $L_2$: the language of all strings where the combinations $*\mathtt 0$ and $*\mathtt 1$ occur equally many times (and, for simplicitly, no other $*$ appears).

Then it is easy to see that $L_1$ is regular and $L_2$ is context free. Therefore their intersection is context free.

Now take a grammar that generates $L_1\cap L_2$, and remove all instances of $*$ from its production rules.