我有几个问题,我不知道如何解决。我知道等价关系是对应于以下属性的关系集:自反、对称、反对称和传递。
1) 考虑字母 Σ = {a,b}。对于哪些语言 L,等价关系 RI 恰好有一个等价类?
2) 让 L 成为字母表上的一种语言(不一定是正则的)。证明如果包含空字符串 [ε] 的等价类不是 {ε},则它是无限的。
3) 考虑字母 Σ = {a,b} 上的语言 L,描述为 L = {x ∈ Σ: |na(x) = nb(x)}。回想一下 na(x) = a'sin x 的数量。
(1) 证明如果 na(x) - nb(x) = na(y) - nb(y),则 xRIy。
(2) 证明如果 na(x) - nb(x) 不 = na(y) - nb(y),则 x 和 y 是 L-可区分的。
(3) 描述RI的所有等价类。