Proving non-regularity of a language

Question

How can I prove $L = (01^n2^n | n\geq 0)$ is not regular?

Would it be sufficient to say that $01^p2^p$ is in $L$ and by pumping lemma, $01^p2^p$ can be written as $xyz$ such that $|y|>0, |xy|\leq p$ and for each $i\geq 0, xy^iz\in L$.

Answer 1

I would suspect just mentioning a string and the pumping lemma is not a full proof that you found a string that cannot be pumped in any way. This is my try:

The string $01^{p}2^{p}$ can be divided in three parts $x$, $y$ and $z$ only in these ways:

1) $x = \epsilon$, $y = 01^{a}$ $|$ $a \geq 0$

If x has length zero, y will always be a zero and some number of 1's. No 2's because then $|xy|$ would be more than $p$. Pumping $y$ will result in strings that have more than one 0 and are thus not in $L$.

2) $x = 01^{a}$ $|$ $a \geq 0$, $y = 1^{b}$ $|$ $b \leq p$

If x is 0, or x is a 0 with some 1's, y consists of only 1's. Pumping y will change the number of 1's and therefore not all strings resulting from this have an equal number of 1's and 2's. Those strings are not in $L$.

Thus the string $01^{p}2^{p}$ cannot be pumped. Since it is in $L$, $L$ is not regular.