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 α
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 .
fuente