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

Question

关闭。这个问题不满足Stack Overflow guidelines .它目前不接受答案。












想改善这个问题吗？更新问题，使其成为 on-topic对于堆栈溢出。

7年前关闭。




Improve this 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 的子集，因此您需要展示的只是一个反例。