# Removing constant symbols from language to prove irregularity

I'm confused about a solution I saw about the following language not being regular:\begin{equation*} L=\{0^n ~1 ~2^n : n >0\} \end{equation*} The example solution said that $L$ was "the same as":\begin{equation*} L'=\{0^n1^n : n > 0 \} \end{equation*} so it wasn't regular. I understand why $L'$ isn't regular, but I don't understand how $L$ is the same as $L'$. How can you eliminate that middle symbol?

The language $L'$ is the "same" as $L$ (in fact, it's an asymmetric relation) in two steps. If $L$ were regular, then so would be $L'' = \{0^n 2^n : n > 0 \}$ (take a DFA for $L$ and replace $1$ edges with $\epsilon$ edges). In its turn, $L''$ is the same as $L'$, up to change of symbols.
• @yuval-filmus It is actually possible to make "the same" a symmetric relation in this case, but it is a little bit more technical. Let $f: \{0, 1, 2\}^* \to \{0, 2\}^*$ be the morphism which erases every $1$. Then $L = f^{-1}(L'') \cap 0^*12^*$. Now regular (and context-free) languages are closed under inverses of morphisms and under intersection with regular sets. Thus if $L''$ were regular, then $L$ would be regular. And if you know that $L''$ is context-free then so is $L$. – J.-E. Pin Oct 16 '13 at 17:15