Implication of the Pumping lemma

Question

I'm reading Hopcroft and Ullman's '79 edition of "Introduction to Automata theory, Languages, and Computation". In chapter 3, the authors say "The lemma[sic] does not state that every sufficiently long string in a regular set is of the form $uv^iw$ for some large $i$". I can't see how this is true.

If I'm not wrong, the pumping lemma states that if $L$ is a regular set, then every "sufficiently" long string $x\in L$ can be written as $uvw$ such that $uv^iw\in L$ for all $i\geq 0$, then shouldn't there be some $i\geq 0$ such that every "sufficiently" long string $x\in L$ be of the form $uv^iw$ for some strings $u,v,w$?

Also, the authors state (whose proof is left as an exercise) that the set $(0+1)^*$ contains arbitrarily long strings in which no substring appears three times consecutively. I can't seem to see how this is true as well.

Any help or perhaps even a hint is well appreciated.

Answer 1

Yes, since we can let $i$ be 0. Every non-empty word $x\in L$ can be expressed as "$xx^0\epsilon$".

We can also let $i$ be 1. Every non-empty word $x\in L$ can be expressed as "$\epsilon x^1\epsilon$".

The statements above are rather trivial and banal.

So, the real question is, given a regular language $L$, is there some $i\geq 2$ such that every "sufficiently" long string $x\in L$ is of the form $uv^iw$ for some strings $u,v,w$ where $v$ is nonempty?

---

The answer is, "not necessarily".

We call a string of the form $vv$ for some non-empty $v$ a square string. There exists an infinite string $t\in \{a,b,c\}^*$ such that it does not contain any square string. An example of such a string is given in this post.

That means there are arbitrary long strings, such as the prefixes of that infinite string, that do not contain any square string. So the answer for the regular language $\{a,b,c\}^*$ is "no".

---

Exercise. Show that every sufficiently long string over the alphabet $\{a,b\}$ is of the form $uv^2w$ for some strings $u,v,w$ where $v$ is nonempty.

---

The set $(0+1)^*$ contains arbitrarily long strings in which no substring appears three times consecutively.

A classical example is the Thue–Morse sequence. For a proof, check a proof to the cube-freeness of the Thue-Morse sequence by Yuval Filmus.