說明兩個正則表示式相等的難題。

問題 1

證明 (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)*

=RHS

於是，這兩個正則表示式相等。

問題 2

證明 (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 的組合}

因此，證明了

LHS=RHS

Bhanu Priya

更新於：2021-6-12

4K+ 次瀏覽量

開啟您的 職業生涯

完成課程獲得認證。

立即開始