题目：
令A、B和C是任意正规式，证明以下关系成立：
A∣A=A
(A*)*= A*
A*=ε∣A A*
(AB)*A=A(BA)*
(A∣B)*=(A*B*)*=(A*∣B*)*
A=b∣aA当且仅当A=a*b
解答：
（1）、A∣A=A
L(A∣A)=L(A)∪L(A)=L(A)，所以有A∣A=A。
（2）、(A*)*= A*
（3）、A*=ε∣A A*
通过证明两个正规式所表示的语言相同来证明两个正规式相等。
L(ε∣A A*)=L(ε)∪L(A)L(A*)= L(ε)∪L(A)(L(A) )*
=L(ε)∪L(A)((L(A))0∪(L(A))1∪(L(A))2∪(L(A))3∪…)
=L(ε)∪(L(A))1∪(L(A))2∪(L(A))3∪(L(A))4∪…
=(L(A))*=L(A*)
即：L(ε∣A A*)=L(A*)，所以有：A*=ε∣A A*
（4）、(AB)*A=A(BA)*
利用正规式的分配率和结合律直接推导。
(AB)*A=((AB)0∣(AB)1∣(AB)2∣(AB)3∣…)A
=εA∣(AB)1A∣(AB)2A∣(AB)3A∣…
=Aε∣A (BA)1∣A (BA)2∣A (BA)3∣…
=A(ε∣(BA)1∣(BA)2∣(BA)3∣…)
=A(BA)*
即：(AB)*A=A(BA)*
（5）、(A∣B)*=(A*B*)*=(A*∣B*)*
证明:先证(A∣B)*=(A*B*)*
因为L(A)L(A) *L(B) *,L(B) L(A) *L(B) *
故:L(A) ∪L(B) L(A) *L(B) *
于是由本题第二小题结论可知(L(A)∪L(B)) *(L(A) *L(B)*)* ①
又L(A)L(A)∪L(B), L(B) L(A)∪L(B)
故:L(A)*(L(A)∪L(B))*
L(B)*(L(A)∪L(B))*
因此有:L(A)*L(B)* (L(A)∪L(B))* (L(A)∪L(B))*=( (L(A)∪L(B))*) 2
故(L(A)*L(B)*)*((L(A)∪L(B))*)*
由本题第二小题得: ((L(A)∪L(B))*)*= (L(A)∪L(B)) *
故得: (L(A)*L(B)*)*(L(A)∪L(B)) * ②
则由①②得: (L(A)∪L(B)) *=(L(A)*L(B)*)*
由于L((A*B*))*=(L(A*B*))*=(L(A*)L(B*))*=(L(A)*L(B)*)*
即有(L(A)∪L(B))*=L((A*B*))* ③
而(A|B)*对应的语言为(L(A)∪L(B))*,且(A*B*)*对应的语言为L((A*B*))*
则根据③得(A|B)*=(A*B*)*
再证:(A*|B*)*=(A*B*)*
因为:A,B是任意正规式,由以上结论得: (A*|B*)*=((A*)*(B*)*)*
又由本题第二小题目的结论可得：（A*）*=A*，（B*）*=B*
因此，（A*|B*）*=（A*B*）*
综合上述两种结论，最后得：(A∣B)*=(A*B*)*=(A*∣B*)*