computation-theory - 使用 Myhill-Nerode 证明语言的非正则性

Question

证明在 {0,1} 上定义的语言，其中 x 的 0 的数量 = x 的 1 的数量是不规则的。

标签： computation-theorydfa

Answer 1

Myhill-Nerode 说，对于一种常规语言，在不可区分关系上的等价类与该语言的最小 DFA 中的状态一样多。

两个字符串 w 和 x 在常规语言 L 中是无法区分的，如果对于任何 y 使得 wy 在 L 中，xy 也在 L 中；如果对于任何 z 使得 xz 在 L 中，wz 也在 L 中。换句话说，如果 w 和 x 可以将完全相同的一组字符串连接到它们以获得 L 中的某个字符串，则它们是无法区分的。

对于您的语言，我们可以证明这种关系下的等价类的数量是无限的。因为没有一个 DFA 有无限多的状态，这是一个矛盾；通过展示这一点，我们表明语言不规则。

在您的情况下，我们可以证明 0^n 与 0^m 是可区分的，因为 m > n，因为可以附加到 0^n 以获得您的语言中的字符串的最短字符串是 1^n，而最短可以附加到 0^m 以获取您的语言的字符串的字符串是 1^m，并且 m > n。因此，每个字符串 0^n 与其他字符串 0^m 是可区分的，n != m，因此有无限多个等价类。正如我们之前所说，这意味着语言不能是规则的。

如果我们发现存在有限数量的等价类并将它们命名，我们也会找到该语言的最小 DFA。只需为每个等价类添加一个状态并找出转换。