Hat jede Saite, die groß genug ist, Wiederholungen?

Sei eine endliche Menge von Zeichen fester Größe. Sei α eine Zeichenkette über Σ . Wir sagen, dass ein nicht leerer Teilstring β von α eine Wiederholung ist, wenn β = γ γ für einen String γ ist .$\Sigma$$\alpha$$\Sigma$$\beta$$\alpha$$\beta = \gamma \gamma$$\gamma$

Nun ist meine Frage, ob das Folgende gilt:

Für jede , existiert ein n ∈ N , so daß für jede Saite α über Σ der Länge mindestens n , α enthält mindestens eine Wiederholung.$\Sigma$$n \in \mathbb{N}$$\alpha$$\Sigma$$n$$\alpha$

Ich habe dies über das binäre Alphabet überprüft, und dies ist in diesem Fall recht einfach, aber ein Alphabet der Größe 3 ist bereits etwas schwieriger zu überprüfen, und ich hätte gerne einen Beweis für beliebig große Grammatiken.

Wenn die obige Vermutung zutrifft, dann kann ich die Forderung nach dem Einfügen leerer Zeichenketten in meine andere Frage (fast) beseitigen .

Nein, leider nicht. Es gibt sogar unendlich viele quadratfreie Wörter, wenn Ihr Alphabet mindestens drei Symbole enthält.

Diese scheinbar natürliche Grenze (Zwei-Elemente-Alphabete haben nur endlich viele quadratfreie Wörter) wird an vielen Stellen beobachtet, zum Beispiel:

• co-finite für | Σ | ≤ 2 aber nicht kontextfrei für Σ > 2 .$\{xyyz \mid x,y,z\in \Sigma^+\}$$|\Sigma|\leq 2$$\Sigma>2$
• $|\Sigma|>3$$|\Sigma|=2$