解释两个正则表达式等价的问题。
问题一
证明(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的任意组合}
因此，证明
左轴=右轴