由'Fibonacci Strings‘生成的语言L(如描述中所给出的)是正规的吗？如果不是，则通过Pumping引理来反驳

Question

斐波那契字符串定义如下: S1=a，S2=b和Sk=S k-1S k-2用于k>2。例如S3=ba、S4=bab等。设L是由Fibonacci字符串生成的语言。语言‘L’是正规的吗？如果不是，则通过Pumping引理来反驳。

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，因此该语言不是常规语言。