使用Myhill-Nerode定理证明语言L非正则的疑问

嘿，你这里的核心误解是把目光局限在L中已经完整的字符串上了，但Myhill-Nerode定理里的“可区分串”并不要求是L的成员——我们需要关注的是那些前缀性的字符串（还没凑够L要求的完整形式的串），通过给它们添加合适的后缀z，来区分它们是否能进入L。

先重新明确一下定理的关键逻辑：如果能找到无穷多个两两可区分的字符串，那语言的等价类就是无穷多的，自然不是正则语言。

回到你的语言 L = { 0^(3n)1^(2n) | n>0 }，它的核心规则是：0的个数是3的倍数，1的个数是2的倍数，且两者满足「0的个数/3 = 1的个数/2 = n」。我们可以这样构造两两可区分的串：

• 取一系列仅由0组成的字符串：x_k = 0^k，其中k是正整数（比如k=1,2,3,4,...）。
• 任取两个不同的k₁和k₂，假设k₁ ≠ k₂ mod 3（比如k₁=1，k₂=2；或者k₁=3，k₂=4），我们来找对应的z：
  比如取k₁=3，k₂=4：我们选z = 0^(3)1^(4)（这里相当于取n=2，需要32=6个0，已经有3个，所以补3个0；对应1的个数是22=4个）。
  • x₁z = 0^3 + 0^31^4 = 0^61^4，显然符合L的形式（n=2），属于L。
  • x₂z = 0^4 + 0^31^4 = 0^71^4，这里0的个数是7（不是3的倍数），1的个数是4，7/3 ≠ 4/2，所以不属于L。

这就说明x₁和x₂是可区分的。更一般地，对于任意两个不同的整数a和b，如果a ≡ r mod 3，b ≡ s mod 3且r≠s，我们总能找到足够大的t，让z=0^(3t - a)1^(2t)，此时x_a z=0^(3t)1^(2t)∈L，而x_b z=0^(b + 3t -a)1^(2t)，因为b -a不是3的倍数，所以总0数不是3的倍数，必然不属于L。

这样一来，我们就找到了无穷多个两两可区分的串（每个不同的模3余数类都能对应无穷多串），说明L的等价类有无穷多个，根据Myhill-Nerode定理，L不是正则语言。

总结一下你之前的误区：你只考虑了给L中已经完整的串加后缀，但定理里的x、y可以是任何Σ*中的串，我们要找的是这些“未完成”的前缀之间的区分性，而不是破坏已有的合法串~

备注：内容来源于stack exchange，提问作者user956293