regex - 确定两种语言是否相等 [正则表达式]

Question

准备考试并且正在经历这个问题：

判断 R1 表示的字符串集合是否是 R2 的子集？

R1 = (01 +10)*      R2 = ((01)* + (10)*)

我的尝试：由于代表相同的表达式，我试图证明它们是相同的 R1 ⊆ R2

我试图证明 R2 与 R1 相同：所以我尝试了这个，使用正则表达式等价定理：

((01 + ε)* + (10 + ε) ) = (01 + ε) + (10 + ε)*

现在我被卡住了，我正在考虑在这里应用关联规则并显示 (01 + ε)* + (10 + ε)* = (01 + 10)* + (ε + ε)* = (01 + 10) * // 我认为这一步可能是错误的

因此 R2 = R1

步骤： (01 + ε)* + (10 + ε)* = (01 + 10)* + (ε + ε)* = (01 + 10)*

我认为是错误的，我认为我应用了错误的结合律，当它上面有 * 时我不知道如何使用它。对此的任何帮助将不胜感激。请 ：）

Answer 1

为了矛盾起见，假设 R1 ⊆ R2。因此，R1 中的每个字符串 s 也在 R2 中。
设 s = "1001"，它是 R1 的成员；但是，s 不是 R2 的成员。=><=

由于 R1 不是 R2 的子集，所以您需要展示的只是一个反例。

Answer 2

我已经有一段时间没有做过证明了，但我认为这里有一个简单的反例证明就足够了。

从断言 R1 是 R2 的子集开始（严格与否无关紧要）。

请注意，R1 可以生成以下字符串（假设+是 OR，因此 R1 可以无限生成其中一个01或任何模式）：10

10 01

您可以观察到不可能在 R2 中生成此字符串，因为 R2 被定义为它必须要么只有01对，要么只有10对。

因此，由于 R1 可以在 R2 的域之外生成字符串，因此 R1 不可能是 R2 的子集，无论是否严格。