Est-ce que chaque chaîne suffisamment grande a des répétitions?

Soit un ensemble fini de caractères de taille fixe. Soit une chaîne sur . Nous disons qu'une sous-chaîne non vide of est une répétition if pour une chaîne .$\Sigma$$\alpha$$\Sigma$$\beta$$\alpha$$\beta = \gamma \gamma$$\gamma$

Maintenant, ma question est de savoir si ce qui suit vaut:

Pour chaque , il existe quelques tels que pour chaque chaîne sur de longueur au moins , contient au moins une répétition.$\Sigma$$n \in \mathbb{N}$$\alpha$$\Sigma$$n$$\alpha$

J'ai vérifié cela sur l'alphabet binaire, et c'est assez facile dans ce cas, mais un alphabet de taille 3 est déjà un peu plus difficile à vérifier, et j'aimerais une preuve pour des grammaires arbitrairement grandes.

Si la conjecture ci-dessus est vraie, je peux (presque) supprimer la demande d'insertion de chaînes vides dans mon autre question .

Non, malheureusement non. Il y a même des mots infinis sans carré si votre alphabet a au moins trois symboles.

Cette frontière apparemment naturelle (les alphabets à deux éléments n'ont que de nombreux mots sans carré) est observée à de nombreux endroits, par exemple:

• $\{xyyz \mid x,y,z\in \Sigma^+\}$ est pour mais pas sans contexte pour .$|\Sigma|\leq 2$$\Sigma>2$
• La classe de langages générée par les modèles sans terminal peut être apprise dans la limite si mais pas si [ Reid2004 ].$|\Sigma|>3$$|\Sigma|=2$