Apakah setiap string cukup besar memiliki pengulangan?

Biarkan menjadi beberapa set karakter terbatas hingga ukuran tetap. Biarkan menjadi string di atas . Kami mengatakan bahwa substring tak kosong dari adalah ulangi jika untuk beberapa string yang .$\Sigma$$\alpha$$\Sigma$$\beta$$\alpha$$\beta = \gamma \gamma$$\gamma$

Sekarang, pertanyaan saya adalah apakah yang berikut ini berlaku:

Untuk setiap , terdapat beberapa sedemikian rupa sehingga untuk setiap string melebihi dengan panjang setidaknya , berisi setidaknya satu pengulangan.$\Sigma$$n \in \mathbb{N}$$\alpha$$\Sigma$$n$$\alpha$

Saya telah memeriksa ini di atas alfabet biner, dan ini cukup mudah untuk kasus itu, tetapi alfabet ukuran 3 sudah agak lebih sulit untuk diperiksa, dan saya ingin bukti untuk tata bahasa besar yang sewenang-wenang.

Jika dugaan di atas benar, maka saya dapat (hampir) menghapus permintaan untuk memasukkan string kosong dalam pertanyaan saya yang lain .

Tidak, sayangnya tidak. Bahkan ada kata - kata bebas persegi tanpa batas jika alfabet Anda memiliki setidaknya tiga simbol.

Batas alami ini (alfabet dua elemen hanya memiliki banyak kata bebas persegi) diamati di banyak tempat, misalnya:

• $\{xyyz \mid x,y,z\in \Sigma^+\}$ adalah co-finite untuk tetapi tidak bebas konteks untuk .$|\Sigma|\leq 2$$\Sigma>2$
• Kelas bahasa yang dihasilkan oleh pola bebas terminal dapat dipelajari dalam batas jika tetapi tidak demikian jika [ Reid2004 ].$|\Sigma|>3$$|\Sigma|=2$