Czy każdy wystarczająco duży ciąg ma powtórzenia?

Niech będzie skończonym zestawem znaków o ustalonym rozmiarze. Niech będzie ciągiem znaków nad . Mówimy, że niepusty substrat z jest powtórzeniem, jeśli dla jakiegoś ciągu .α Σ β $\Sigma$$\alpha$$\Sigma$$\beta$$\alpha$$\beta = \gamma \gamma$$\gamma$

Teraz moje pytanie dotyczy tego, czy:

Dla każdego istnieje pewna liczba taka, że ​​dla każdego łańcucha powyżej o długości co najmniej , zawiera co najmniej jedno powtórzenie.$\Sigma$ α Σ n $n \in \mathbb{N}$$\alpha$$\Sigma$$n$$\alpha$

Sprawdziłem to za pomocą binarnego alfabetu i jest to dość łatwe w tym przypadku, ale alfabet wielkości 3 jest już nieco trudniejszy do sprawdzenia, a chciałbym dowód na dowolnie duże gramatyki.

Jeśli powyższa hipoteza jest prawdziwa, mogę (prawie) usunąć żądanie wstawienia pustych ciągów w moim drugim pytaniu .

Nie, niestety nie. Istnieją nawet nieskończone słowa bez kwadratów, jeśli twój alfabet ma co najmniej trzy symbole.

Ta pozornie naturalna granica (dwuelementowe alfabety mają tylko skończoną liczbę słów bez kwadratów) jest obserwowana w wielu miejscach, na przykład:

• $\{xyyz \mid x,y,z\in \Sigma^+\}$ jest współ-skończony dla ale nie jest kontekstowy dla .Σ > $|\Sigma|\leq 2$$\Sigma>2$
• Klasy języków generowanych przez wzorce bez terminala można nauczyć się w limicie, jeśli ale nie tak, jeśli [ Reid2004 ].| Σ | = $|\Sigma|>3$$|\Sigma|=2$