Problem Detail: Let $Sigma$ be some finite set of characters of fixed size. Let $alpha$ be some string over $Sigma$. We say that a nonempty substring $beta$ of $alpha$ is a repeat if $beta = gamma gamma$ for some string $gamma$. Now, my question is whether the following holds:
For every $Sigma$, there exists some $n in mathbb{N}$ such that for every string $alpha$ over $Sigma$ of length at least $n$, $alpha$ contains at least one repeat.
I’ve checked this over the binary alphabet, and this is quite easy for that case, but an alphabet of size 3 is already quite a bit harder to check, amd I’d like a proof for arbitrarily large grammars. If the above conjecture is true, then I can (almost) remove the demand for inserting empty strings in my other question.
Asked By : Alex ten Brink
Answered By : Raphael
No, unfortunately not. There are even infinite square-free words if your alphabet has at least three symbols. This apparently natural border (two-element alphabets have only finitely many square-free words) is observed in many places, for instance:
- ${xyyz mid x,y,zin Sigma^+}$ is co-finite for $|Sigma|leq 2$ but not context-free for $Sigma>2$.
- The class of languages generated by terminal-free patterns can be learned in the limit if $|Sigma|>3$ but not so if $|Sigma|=2$ [Reid2004].
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/757
