regular-language - 强化学习当量比

Question

我需要帮助解决一些 2 个问题，谢谢帮助 会有 L ⊆ Σ* ，证明或反驳： 1. 如果每个 RL 等价类是正则语言，则 RL 包含无限等价类 2. 如果 L 是正则语言，则 RL 包含一个无限等价类

RL：x RL y（对于 Σ* 中的每个 z，当且仅当 yz L 中的 xz）

Answer 1

1. 如果每个 RL 等价类都是正则语言，则 RL 包含一个无限等价类

考虑语言 0^(2^n) for n >= 0: 0, 00, 0000, ...。这种语言中的每个字符串都是可区分的：每个等价类都由一个字符串组成。有限语言总是规则的。因此，我们将每个 RL 等价类作为常规语言，但没有一个 RL 等价类是无限的。因此，该主张是错误的，已被反例证伪。

2. 如果 L 是正则语言，则 RL 包含无限等价类

因为 L 是正则的，所以我们知道在 RL 下有有限多个等价类——事实上，我们知道在语言的最小确定性有限自动机中，每个状态都有一个。因为字母表上的所有无限多的字符串都必须属于这些等价类之一，所以至少有一个类必须包含无限多的这些字符串。假设情况并非如此；那么等价类 1、2、...、p 仅包含 c[1]、c[2]、...、c[p] 字符串。但是只有 c[1] + c[2] + ... + c[p] 字符串在等价类中。这个数字是有限的，所以我们一定错过了一些字符串。因此，该主张是正确的，已被矛盾证明。