解释两个正则表达式等价的问题。

问题一

证明(1+00*1)+(1+00*1)(0+10*1)*(0+10*)=0*1(0+10*1)*

解决方案

这里，我们需要证明 LHS=RHS（左手边 = 右手边）

让我们先解决LHS

(1+00*1)+(1+00*1)(0+10*1)*(0+10*)

以(1+00*1)为公因数

(1+00*1)(ε+(0+10*1)*(0+10*1)

在哪里，

(0+10*1)*(0+10*1)。它是 R*R 的形式，其中 R=0+10*1

众所周知，(ε+R*R)=(ε+RR*)=R*

所以，

(1+00*1)((0+10*1)*)

以1为公因数

(ε+00*)1(0+10*1)*

应用ε+00*=0*

0*1(0+10*1)*

=右侧

因此，两个正则表达式是相等的。

问题二

证明(0*1*)*=(0+1)*

解决方案

考虑 LHS

(0*1*)*= { ε,0,00,1,11,111,01,10,……}

= {0 的任意组合，1 的任意组合，0 和 1 的任意组合，ε}

相似地，

RHS=(0+1)*

= { ε,0,00,1,11,111,01,10,.....}

= { ε，0 的任意组合，1 的任意组合，0 和 1 的任意组合}

因此，证明

左轴=右轴