automation - 由“斐波那契字符串”（如说明中给出的）生成的语言 L 是否正常？如果不是，则通过 Pumping Lemma 反驳

Question

斐波那契字符串定义如下： S1=a, S2=b 和 Sk=S k-1S k-2 for k>2 。例如 S3=ba ， S4=bab 等。令 L 为斐波那契字符串生成的语言。语言'L'是规则的吗？如果不是，请通过 Pumping Lemma 反驳。

Answer 1

考虑这种语言中字符串的长度。它们本身就是斐波那契数列。考虑 S(i)，这个集合中的第 i 个字符串。它的长度为 F(i)，其中 F(i) 是第 i 个斐波那契数。

现在考虑 S(i+1)，长度为 F(i+1) 的语言中的第 (i+1) 个字符串。我们可以将哪些字符串附加到该语言中以获取该语言中的另一个字符串？当然，我们可以附加空字符串。我们可以附加的下一个最小字符串是 S(i) 以获得 S(i+2)。S(i) 的长度为 F(i)。因此，我们可以附加到语言中的任何给定字符串以获得该语言中的另一个字符串的第二最短字符串对于每个 S(i) 都是唯一的；因此，根据 Myhill-Nerode 定理，它们都是可区分的，并且该语言的最小 DFA 将需要无限多个状态来区分它们。由于 DFA 不能有无限多的状态，因此该语言没有 DFA，并且由于该语言没有 DFA，因此该语言不是正则的。