正则表达式简化问题

Question

我试图理解下面定义的正则表达式 α 和 β 之间的等价性，但我对相互矛盾的信息失去了理智。

a+b:   a or b
ab:    concatenation of a and b
$:     empty string

α = (1*+0)+(1*+0)(0+1)*($+0+1)

β = (1*+0)(0+1)*($+0+1)

https://ivanzuzak.info/noam/webapps/regex_simplifier/ 表示，α 等同于 β.

然而，我的学校教导说串联比并集具有更强的绑定，这意味着：

11*+0 =/= 1(1*+0)

这意味着我的 α 看起来像这样带括号：

α= (1*+0) + ( (1*+0)(0+1)*($+0+1) )

还有那个

α=/=((1*+0)+(1*+0))(0+1)* ($+0+1)

我希望您清楚我的问题是什么，如果有任何帮助，我将不胜感激。谢谢

Answer 1

通常，当两个正则表达式匹配同一组单词时，它们被认为是等价的。

他们如何匹配是不相关的。因此，哪个运算符具有更高的优先级并不重要。

注意相等（书面形式）和等价（具有相同效果）之间的细微差别。

Answer 2

好吧，原来是我误会了为什么b+b <=> b。

如果L1是L2的子集，则L1∪L2 <=> L2。