*1.理解如下正則表達(dá)式，說明它們表示的語言（1）(00+11)+表示的語言特征是0和1都各自成對出現(xiàn)（2）(1+0)*0100+表示的語言特征是以010后接連續(xù)的0結(jié)尾（3）(1+01+001)*(e+0+00) 表示的語言特征是不含連續(xù)的3個(gè)0（4）(0+1)(0+1)*+ (0+1)(0+1)(0+1)* 表示所有長度為3n或2m的0，1串（n0,m0）（5）(0+1)(0+1)* (0+1)(0+1)(0+1)* 表示所有長度為3n+2m的0，1串（n0,m0）（6）00+11+（01+10）（00+11）*（10+01）表示的語言特征為長度為偶數(shù)n的串.當(dāng)n=2時(shí)，是00或11的串。n4時(shí)，是以01或10開頭，中間的子串00或11成對出現(xiàn)，最后以10或01結(jié)尾的串*2.證明下列各式 褚穎娜 02282072（1）結(jié)合律 (rs)t=r(st) (r+s)+t= r+(s+t)1）證明 對 x(rs)t 總可以找到一組x1 x2 x3 使得 x=x1x2x3 其中x3t x1x2rs 且 x1r, x2s,則 x2x3st 因此x1(x2x3)r(st) 即 x1x2x3r(st) xr(st)得證 因此 (rs)tr(st)同理可證r(st) (rs)t 則 (rs)t=r(st) 成立2) 證明 對x(r+s)+t x(r+s)或xt 對于xr+sxr或rs ，因此xr或xs或xtxr或x(s+t) xr+(s+t)所以(r+s)+t r+(s+t)同理可證r+(s+t) (r+s)+t則(r+s)+t= r+(s+t) 成立（2）分配律 r(s+t)=rs+rt (s+t)r=sr+tr1) 證明 對于xr(s+t) 總可以找到x1 x2 使得x=x1x2 其中x1r, x2（s+t）由x2（s+t） x2s或x2t則x1x2rs或x1x2rt所以r(s+t)rs+rt對于xrs+rt xrs或xrt 且總可以找到一組x1 x2 使得x=x1x2 其中x1r, x2s或x1r, x2tx1r，x2s或x2t x1r，x2(s+t) x1x2r(s+t)所以rs+rtr(s+t)則r(s+t)=rs+rt2) 證明 對于x(s+t)r 總可以找到x1 x2 使得x=x1x2 其中 x1（s+t），x2r由x1（s+t） x1s或x1t則x1x2sr或x1x2tr所以(s+t)rsr+tr對于xsr+tr xsr或xtr 且總可以找到一組x1 x2 使得x=x1x2 其中x1s, x2r或x1t, x2r x1s或x1t, x2r x1(s+t) ,x2r x1x2(s+t)r所以sr+tr (s+t)r則(s+t)r=sr+tr(3)交換律 r+s=s+r 證明 對于 xr+sxr或xsxs或xrxs+r 所以r+ss+r 同理可證s+rr+s則r+s=s+r（4）冪等律 r+r=r 證明 對于 xr+r xr或xr xr 所以r+rr對于 xrxr或xrxr+r 所以rr+r 因此 r+r=r（5）加法運(yùn)算零元素：r+F=r 證明 對于 xr+F xr或xF xr 所以r+Fr對于 xrxr或xFxr+F 所以rr+F因此 r+F=r(6) 乘法運(yùn)算單位元：r=r=r證明：對xR xe=ex=x Re=eR=R re=er=r(7)乘法運(yùn)算零元素：r=r=證明：對xR x=x= R=R=R r=r=(8) F*=證明F*=F0F1F2F3.=F1F2F3.=(9) (r+)*=r*由第一章的作業(yè)1.30中的第九題 (L1)*=L1*其中L1為正則語言又r為正則表達(dá)式 正則語言可以用正則表達(dá)式表示，因此顯然有(r+)*=r*成立(10) (r*s*)*=(r+s)*由第一章的作業(yè)1.30中的第八題 (L2L1)*=( L2* L1*)* 其中L1、L2 為正則語言又r、s為正則表達(dá)式 正則語言可以用正則表達(dá)式表示，因此顯然有(r+s)*= (r*s*)*成立 即(r*s*)*=(r+s)*成立(11) (r*)*=r*由第一章的作業(yè)1.30中的第三題 (L1*)*= L1*其中L1為正則語言又r為正則表達(dá)式 正則語言可以用正則表達(dá)式表示，因此顯然有(r*)*= r*成立*3下面各式成立嗎？請證明你的結(jié)論(1) (r+rs)*r=r(sr+r)*證明：成立。如果對所有的k=0, (r+rs)k r=r(sr+r)k 成立，則(r+rs)*r=r(sr+r)*肯定成立可以用歸納法證明(r+rs)k r=r(sr+r)k對所有的k=0成立I. k=0時(shí)候，(r+rs)0 r=r= r(sr+r)0II. 假設(shè)k=n時(shí)候(r+rs)nr=r(sr+r)n成立，往證k=n+1時(shí)候結(jié)論成立 (r+rs)n+1r=(r+rs)n (r+rs)r=(r+rs)n (rr+rsr)= (r+rs)n r (r+sr)= r(sr+r)n (r+sr)= r(sr+r)n (sr+r)= r(sr+r)n+1這就是說，結(jié)論對k=n+1成立，即證明了(r+rs)k r=r(sr+r)k對所有的k=0成立，所以(r+rs)*r=r(sr+r)*(2) t(s+t)r=tr+tsr證明：不成立。不妨取r=0,s=1,t=2,則t(s+t)r=2(1+2)0=210+230,但tr+tsr=20+210.(3) rs=sr證明：不成立。不妨取r=0,s=1,顯然rs=01,而sr=10.(4) s(rs+s)*r=rr*s(rr*s)*不成立，假設(shè)r,s分別是表示語言R，S的正則表達(dá)式，例如當(dāng)R=0，S=1, L(s(rs+s)*r)是以1開頭的字符串，而L(rr*s(rr*s)*)是以0開頭的字符串.L(s(rs+s)*r) L(rr*s(rr*s)*)所以s(rs+s)*r rr*s(rr*s)*,結(jié)論不成立(5)(r+s)*=(r*s*)*證明：結(jié)論成立。I. L(r+s)=L(r)L(s), L(r)=L(rs0)L(r*s*), L(s)=L(r0s)L(r*s*)那么L(r+s)=L(r)L(s) L(r*s*)，(L(r+s)* (L(r*s*)*,L(r+s)*) L( (r*s*)* ),所以(r+s)* (r*s*)*II. (r+s)*= (r+s)*)*,對任意m,n=0,rmsn (r+s)m+n ，所以r*s*(r+s)*(r*s*)*(r+s)*)*= (r+s)*由I，II可以知道(r*s*)*(r+s)*，(r+s)* (r*s*)*得到(r+s)*=(r*s*)* (6)(r+s)*=r*+s*不成立，假設(shè)r,s分別是表示語言R，S的正則表達(dá)式，例如當(dāng)R=0