每个足够大的字符串都有重复吗？

Question

令$ sigma $为固定尺寸的一组有限的字符。令$ alpha $为$ sigma $的某些字符串。我们说$ alpha $ of $ alpha $的非空sudstring $ beta $是一个 重复 如果$ beta = gamma gamma $对于某些字符串$ gamma $。

现在，我的问题是以下内容是否存在：

对于每一个$ sigma $，都存在 mathbb {n} $中的一些$ n ，以使每个字符串$ alpha $ to $ sigma $长度至少$ n $，$ n $，$ alpha $至少包含一个重复。

我已经通过二进制字母对此进行了检查，对于这种情况来说，这很容易，但是Size 3的字母已经很难检查，AMD我希望有一个任意大型语法的证明。

如果上述猜想是正确的，那么我可以（几乎）删除插入空字符串的需求 在我的另一个问题中.

Answer 1

不，不幸的是不是。甚至有无限 无方 单词如果您的字母至少具有三个符号。

例如，在许多地方观察到这个显然自然的边界（两元素字母仅有一定的无平方单词）：

• $ {xyyz mid x，y，y，z in sigma^+} $是$ | sigma | leq 2 $的co-finite，但对于$ sigma> 2 $而不是上下文。
• 无终端生成的语言类 图案 可 学到极限 如果$ | sigma |> 3 $，则不是$ | sigma | = 2 $ [REID2004].