1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

You’re starting with the right sort of word, but the last paragraph doesn’t really make sense.

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?)

$\endgroup$

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.