1
$\begingroup$

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?

$\endgroup$
4
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ @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$. $\endgroup$ – J.-E. Pin Oct 16 '13 at 17:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for?Browse other questions tagged or ask your own question.