regular-language - 努力了解 Myhill-Nerode

Question

我想我知道抽水引理，并被告知 Myhill-Nerode 是一种非常优雅的方式来表明某事物是规则的还是不规则的。但我遇到了很多麻烦。以此为例：

= {0 ^k , k = 2 ⁿ , n >̲ 1}

我的语言是从 0 到 2 的幂的长度的重复。我想使用 Myhill-Nerode 来表明这是规则的还是不规则的。可能吗？

我知道如何将其设置为类似于其他 Myhill-Nerode 外观证明，但我不太了解等效概念。

我可以说我有一些和where ≠并且两者都是 2 ^h和的形式，然后我定义，这样：

= 0 ^j/2

= 0 ^p/2

= 0 ^j/2

其中= 0 ^j/2 0 ^j/2 = 0 ^j是我的语言，因为它的形式是 2 ⁿ，但是 = 0 ^p/2 0 ^j/2不能保证每个 p 和 j 都是我的语言，因为≠

Answer 1

给定语言 L，如果对于所有字符串 w 属于 sigma，两个字符串 u, v 2 L 是等价的 * 我们有 uw 属于 L 当且当 vw 属于 L

考虑 {0,0^2,0^4,0^8....} 的集合，在这种情况下，对于某些 m 和 n，0^m 和 0^n 应该映射到相同的等价类，否则存在根据 Myhill-Nerode 定理，将是无限等价类，使其不规则。然而 0^m.0^m 属于 L 但 0^n.0^m 不会..因此