# Using pumping lemma to prove a set of substrings cannot be expressed as a regular expression…

I'm trying to use the Pumping Lemma of regular expressions to prove the set of all finite substrings in the infinite string 012001122000111222000011112222... is not regular. E.g. 0120 and 20001 are substrings of it, 0122 and 111220 are not.

I'm thinking I can use 0k1k2k which is in the language.

And then by picking the shortest x for the pumping lemma it must be a non-empty string of 0s say length p 0k1k2k+p which would give 0122 at very least, and therefore is not in the language. Is this the correct method or is this completely wrong.

HINT: Assume that the language is regular, let $p$ be the pumping length, and start with the word $0^p1^p2^p$. The pumping lemma says that this can be decomposed as $xyz$ in such a way that $|xy|\le p$, $|y|\ge 1$, and $xy^kz$ is in the language for each $k\ge 0$. Show that if $k>1$, $xy^kz$ is not in the language.
It will be helpful to write out exactly what $xy^kz$ is. Start by noting that there are integers $r\ge 0$ and $s\ge 1$ such that $x=0^r$ and $y=0^s$. (Why?)