Proving ${0^n 1^n 2^n | n >= 0}$ is not regular

Question

This is not a homework assignment, but something I'm reviewing.

I need to prove that $0^n 1^n 2^n$ where $n \geq 0$ is not regular (Just the DFA, not related to CFG). I feel like this is similar to proving $0^n1^n$ is not regular because all you have to do is pump the 0's and then the size of each digit doesn't match so the language isn't regular.

But in this solution (page 3), I understood only up to $xy = 0^k$. If I had continue from this, I would have said "If you have the string $xyyz$, then the string will have more $0$'s then $1$'s and $2$'s. The variable $y$ has to have at least one $0$ in it (because of the pumping lemma condition), so adding one more $y$ will add a $0$ breaking the language and reaching a contradiction. "

Is there anything wrong with my approach?

From the pdf, I see they then broke up the string into $x=0^a y= 0^b z=0^c 1^p 2^p$. Then by setting $i=0$, they show that $|y|$ will equal $0$ when it shouldn't because of the pumping lemma. I guess they wanted to show a pumped down version?

Answer 1

Your approach is a bit informal but basically correct: in this case you can pump in either direction and get a contradiction. It’s a good idea, though, to learn how to write it up more carefully, along the lines used in that PDF. You might write something like this, for instance:

We have $xy=0^k$, where $1\le k\le p$. This means that $x=0^a$, $y=0^b$, and $z=0^c1^p2^p$ for some non-negative integers $a,b$, and $c$ such that $b>0$, $a+b=k$, and $a+b+c=p$. Now let $s'=xy^iz$; then $$s'=0^a(0^b)^i0^c1^p2^p=0^{a+bi+c}1^p2^p\;.$$ But $b>0$, so $a+bi+c=a+b+c=p$ if and only if $i=1$, i.e., $s'\in A_1$ if and only if $i=1$. This contradicts the conclusion of the pumping lemma and so shows that $A_1$ is not regular.

Or if you just wanted a more careful version of your argument, you could replace the last bit with this:

Now let $s'=xy^2z$; then $$s'=0^a0^{2b}0^c1^p2^p=o^{a+2b+c}1^p2^p\;.$$ But $b>0$, so $a+2b+c>a+b+c=p$, and therefore $s'\notin A_1$. This contradicts the conclusion of the pumping lemma and so shows that $A_1$ is not regular.

Answer 2

Homomorphisms preserve regularity. That means that if $h$ is a homomorphism and $L$ is a regular language then $h(L)$ is also regular. In your case you can take the homomorphism $h(0) = 0$, $h(1) = 1$, $h(2) = \epsilon$ which maps your language to the language $L' = \{ 0^n 1^n : n \geq 0 \}$, which you already know is not regular; if your language was regular, then so would $L'$ be, and this contradiction shows that your language is not regular.

---

What is a homomorphism? It is a mapping from $\Sigma$ to $\Sigma^*$. In other words, it is a mapping that maps each alphabet symbol to some word. For example, the homomorphism described above maps the symbols $0,1$ to themselves and $2$ to the empty word.

Given a homomorphism $h$, we can apply it to a word as follows $h(w_1\ldots w_n) = h(w_1)\ldots h(w_n)$. Here $w_1,\ldots,w_n$ are symbols forming the word $w_1\ldots w_n$. In words, we apply the homomorphism to each symbol, and concatenate the results.

Given a homomorphism $h$, we apply it to an entire language by applying it to each of the words in the language. For example, $$h(\{0^n1^n2^n:n \geq 0\}) = \{h(0^n1^n2^n):n \geq 0\} = \{0^n1^n:n \geq 0\}.$$

If a language $L$ is regular and $h$ is a homomorphism then $h(L)$ is also regular. The easiest way to see that is by taking a regular expression for $L$ and applying the homomorphism to it. Therefore if $h(L)$ is not regular, $L$ also cannot be regular.

---

A related operation is inverse homomorphism. For a homomorphism $h$ and a language $L$, the language $h^{-1}(L)$ consists of all words $w$ such that $h(w) \in L$. If $L$ is regular then so is $h^{-1}(L)$. One way to see that is by taking an NFA for $L$ and replacing each edge labeled $\sigma$ by a path labeled $h(\sigma)$.