展示语言是有规律的

Question

所以我正在尝试解决这样的问题： 证明由斐波那契长度的二进制数符合的语言不是常规语言。

我真的不知道如何处理它，也不确定我是否理解它。

Answer 1

长度为斐波那契数的二进制数的语言可以通过泵引理或 Myhill-Nerode 定理显示为不规则的。

对于抽水引理，取任何字符串 0^p，其中 p 是抽水长度。无论你考虑哪个子串，你都会在相当短的时间内得到一个矛盾（对于 p > 1，从来没有 p - a、p 和 p + a 都是斐波那契数列。这一事实的证明可参考斐波那契数列的定义。

对于 Myhill-Nerode 定理证明，只需证明对于长度为第 n 个斐波那契数的任意字符串 x，可以追加得到更多的最小非空字符串该语言中的字符串的长度等于第 (n-1) 个斐波那契数。因此，有无限多个可区分的字符串，因此，语言不是规则的（因为在不可区分关系下每个等价 class 有一个状态的最小 DFA 必须有有限多个状态）。