Toda string grande o suficiente tem repetições?

20

Vamos haver algum conjunto finito de caracteres de tamanho fixo. Seja α um fio acima de Σ . Dizemos que um substrato não vazio β de α é uma repetição se β = γ γ para alguma cadeia γ .ΣαΣβαβ=γγγ

Agora, minha pergunta é se o seguinte vale:

Para cada , existe algum n N, de modo que, para cada string α acima de Σ de comprimento, pelo menos n , α contenha pelo menos uma repetição.ΣnNαΣnα

Eu verifiquei isso no alfabeto binário, e isso é bastante fácil para esse caso, mas um alfabeto de tamanho 3 já é um pouco mais difícil de verificar, e eu gostaria de uma prova de gramáticas arbitrariamente grandes.

Se a conjectura acima for verdadeira, eu posso (quase) remover a demanda por inserir cadeias vazias na minha outra pergunta .

Alex ten Brink
fonte

Respostas:

15

Não, infelizmente não. Existem até infinitas palavras livres de quadrados se o seu alfabeto tiver pelo menos três símbolos.

Essa borda aparentemente natural (alfabetos de dois elementos tem apenas finitas palavras sem quadrados) é observada em muitos lugares, por exemplo:

  • é co-finito para | Σ | 2, mas não isento de contexto para Σ > 2 .{xyyzx,y,zΣ+}|Σ|2Σ>2
  • |Σ|>3|Σ|=2
Rafael
fonte
Droga, isso é muito ruim, então: S
Alex ten Brink