{a, b} 中的 RL 关系中有多少等价物 类 | (#a(w) mod m) = ((#b(w)+1) mod m)}

Question

的 RL 关系中有多少等价物 类

{w in {a, b}* | (#a(w) mod m) = ((#b(w)+1) mod m)}

我正在查看过去的测试题，其中提供了选项

• m(m+1)
• 2米
• m^2
• m^2+1
• 无限

但是，我声称它是 m，我想出了一个自动机，我相信它接受这种包含 3 个状态的语言（对于 m=3）。

我说得对吗？

Answer 1

其实你是对的。要看到这一点，请注意#a(w) 和#b(w) 的差异，#a(w) - #b(w) modulo m，才是最重要的；并且这个差模 m 只有 m 个可能的值。因此，m 个状态总是足以接受这种形式的语言：只需将相应于适当差异的状态设为接受状态即可。

在您的 DFA 中，a2 对应于零差值，a1 对应于一差值，a3 对应于二差值。