2
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ I think the author is trying to make clear that "not all partition" uvw of all sufficiently long string could be pumped. According to lemma "there exist" some partition uvw "for all" sufficiently long strings that can be pumped. $\endgroup$
    – aispark
    Aug 28 '21 at 17:41
  • $\begingroup$ @m c squared - Yes I'm aware of that $\endgroup$ Aug 29 '21 at 12:04
3
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Woah, this is an interesting answer!, Thanks for your time:) $\endgroup$ Aug 29 '21 at 12:02

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.