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

20

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 .ΣαΣβαβ=γγγ

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.ΣnNαΣnα

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 .

Alex ten Brink
la source

Réponses:

15

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:

  • {xyyzx,y,zΣ+} est pour mais pas sans contexte pour .|Σ|2Σ>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 ].|Σ|>3|Σ|=2
Raphael
la source
Merde, c'est dommage alors: S
Alex ten Brink