¿Cada cadena lo suficientemente grande tiene repeticiones?

20

Deje que sea ​​un conjunto finito de caracteres de tamaño fijo. Deje que sea ​​una cadena sobre . Decimos que una subcadena no vacía de es una repetición if para alguna cadena .α Σ β αΣαΣβαγβ=γγγ

Ahora, mi pregunta es si se cumple lo siguiente:

Para cada , existen algunos tal manera que para cada cadena sobre de longitud al menos , contiene al menos una repetición.n N α Σ n αΣnNαΣnα

He comprobado esto sobre el alfabeto binario, y esto es bastante fácil para ese caso, pero un alfabeto de tamaño 3 ya es un poco más difícil de verificar, y me gustaría una prueba de gramáticas arbitrariamente grandes.

Si la conjetura anterior es cierta, entonces puedo (casi) eliminar la demanda de insertar cadenas vacías en mi otra pregunta .

Alex ten Brink
fuente

Respuestas:

15

No, desafortunadamente no. Incluso hay infinitas palabras sin cuadrados si su alfabeto tiene al menos tres símbolos.

Este borde aparentemente natural (los alfabetos de dos elementos solo tienen finitamente muchas palabras sin cuadrados) se observa en muchos lugares, por ejemplo:

  • | Σ | 2 Σ > 2{xyyzx,y,zΣ+} es co-finito para pero no está libre de contexto para .|Σ|2Σ>2
  • La clase de lenguajes generados por patrones sin terminal se puede aprender en el límite si pero no así si [ Reid2004 ].| Σ | = 2|Σ|>3|Σ|=2
Rafael
fuente
Maldición, eso es muy malo entonces: S
Alex ten Brink