1、文檔供參考，可復制、編制，期待您的好評與關注！ 1.寫出表示下列語言的正則表達式。 （吳賢珺 02282047） 0, 1*。解：所求正則表達式為：(0+1)*。 0, 1+。解：所求正則表達式為：(0+1)+。 xx0,1+ 且x中不含形如00的子串 。解：根據第三章構造的FA，可得所求正則表達式為：1*(01+)*(01+0+1)。 xx0,1*且x中不含形如00的子串 。解：根據上題的結果，可得所求正則表達式為：+1*(01+)*(01+0+1)。 xx0,1+ 且x中含形如10110的子串 。解：所求正則表達式為：(0+1)*10110(0+1)*。 xx0,1+ 且x中不含形如101

2、10的子串 。解：根據第三章的習題，接受x的FA為：S0110q0q1q2101110q3q4要求該FA對應的正則表達式，分別以q0、q1、q2、q3、q4為終結狀態考慮：q0為終態時的正則表達式：(0*(11*0(10)*(+111*11*0(10)*)0)*)*q1為終態時的正則表達式：0*1(1*(0(10)*111*1)*(0(10)*00*1)*)*q2為終態時的正則表達式：0*11*0(10)*(111*11*0)*(00*11*0)*)*q3為終態時的正則表達式：0*11*0(10)*1(11*11*0(10)*(00*11*0)*)*1)*q4為終態時的正則表達式：0*11*0

3、(10)*11(1*(11*0(00*11*0)*(10)*)*11)*)*將以上5個正則表達式用“+”號相連，就得到所要求的正則表達式。 xx0,1+ 且當把x看成二進制數時，x模5與3同余和x為0時，x=1且x0時，x的首字符為1。解：先畫出狀態轉移圖，設置5個狀態q0、q1、q2、q3、q4，分別表示除5的余數是0、1、2、3、4的情形。另外，設置一個開始狀態q.由于要求x模5和3同余，而3模5余3,故只有q3可以作為終態。由題設，x=0時，x=1，模5是1，不符合條件，所以不必增加關于它的狀態。下面對每一個狀態考慮輸入0和1時的狀態轉移。q: 輸入1，模5是1，進入q1。q0: 設x=

4、5n。輸入0，x=5n*2=10n，模5是0，故進入q0輸入1，x=5n*2+1=10n+1，模5是1，故進入q1q1：設x=5n+1。輸入0，x=(5n+1)*2=10n+2，模5是2，故進入q2 輸入1，x=(5n+1)*2+1=10n+3，模5是3，故進入q3q2：設x=5n+2。輸入0，x=(5n+2)*2=10n+4，模5是4，故進入q4 輸入1，x=(5n+2)*2+1=10n+5，模5是0，故進入q0q3：設x=5n+3。輸入0，x=(5n+3)*2=10n+6，模5是1，故進入q1 輸入1，x=(5n+3)*2+1=10n+7，模5是2，故進入q2q4：設x=5n+4。輸入0，

5、x=(5n+4)*2=10n+8，模5是3，故進入q3 輸入1，x=(5n+4)*2+1=10n+9，模5是4，故進入q4則狀態轉移圖如下：q1q1S01q2q30q410101q001則所求的正則表達式為：1(010*1+(1+001*0)(101*0)*(0+110*1)*(1+001*0)(101*0)* xx0,1+ 且x的第10個字符是1 。解：所求正則表達式為：(0+1)91(0+1)*。 xx0,1+ 且x以0開頭以1結尾 。解：所求正則表達式為：0(0+1)*1。 xx0,1+ 且x中至少含兩個1 。解：所求正則表達式為：(0+1)*1(0+1)*1(0+1)*。 xx0,1*

6、和如果x以1結尾，則它的長度為偶數；如果x以0結尾，則它的長度為奇數。解：所求正則表達式為：(0+1)2n+11+(0+1)2n0 (nN)或0+(0+1)(0+1)(0+1)*1+(0+1)(0+1)(0+1)(0+1)*0。 xx是十進制非負實數 。解：首先定義 .,0,1,2,3,4,5,6,7,8,9則所求正則表達式為：(0+1+9)*. (0+1+9)*。 。解：所求正則表達式為：。 。解：所求正則表達式為：。*2.理解如下正則表達式，說明它們表示的語言（1）(00+11)+表示的語言特征是0和1都各自成對出現（2）(1+0)*0100+表示的語言特征是以010后接連續的0結尾（3）

7、(1+01+001)*(e+0+00) 表示的語言特征是不含連續的3個0（4）(0+1)(0+1)*+ (0+1)(0+1)(0+1)* 表示所有長度為3n或2m的0，1串（n³0,m³0）（5）(0+1)(0+1)* (0+1)(0+1)(0+1)* 表示所有長度為3n+2m的0，1串（n³0,m³0）（6）00+11+（01+10）（00+11）*（10+01）表示的語言特征為長度為偶數n的串.當n=2時，是00或11的串。n³4時，是以01或10開頭，中間的子串00或11成對出現，最后以10或01結尾的串*4.3.證明下列各式 褚穎娜 0

8、2282072（1）結合律 (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)tÍr(st)同理可證r(st)Í (rs)t 則 (rs)t=r(st) 成立2) 證明 對"x(r+s)+t x(r+s)或xt 對于xr+sÞxr或rs ，因此xr或xs或xtÞxr或x(s+t) 

9、2; 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, x2tÞx

10、1r，x2s或x2tÞ x1r，x2(s+t)Þ x1x2r(s+t)所以rs+rtÍr(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)rÍsr+tr對于"xsr+tr Þxsr或xtr 且總可以找到一組x1 x2 使得x=x1x2 其中x1s, x2r或x1t, x2rÞ x1s或x1t, x2rÞ x1(s+t) ,x2r

11、22; x1x2(s+t)r所以sr+tr Í(s+t)r則(s+t)r=sr+tr(3)交換律 r+s=s+r 證明 對于 "xr+sÞxr或xsÞxs或xrÞxs+r 所以r+sÍs+r 同理可證s+rr+s則r+s=s+r（4）冪等律 r+r=r 證明 對于 " xr+rÞ xr或xrÞ xr 所以r+rÍr對于 "xrÞxr或xrÞxr+r 所以rÍr+r 因此 r+r=r（5）加法運算零元素：r+F=r 證明 對于 " xr+F

12、2; xr或xFÞ xr 所以r+FÍr對于 "xrÞxr或xFÞxr+F 所以rÍr+F因此 r+F=r(6) 乘法運算單位元：r=r=r證明：對"xÎR xe=ex=x Re=eR=R re=er=r(7)乘法運算零元素：rÆ=Ær=Æ證明：對"xÎR xÆ=Æx=Æ RÆ=ÆR=R rÆ=Ær=Æ(8) F*=證明F*=F0F1F2F3.=F1F2F3.=(9) (r+)*=r*由

13、第一章的作業1.30中的第九題 (L1)*=L1*其中L1為正則語言又r為正則表達式 正則語言可以用正則表達式表示，因此顯然有(r+)*=r*成立(10) (r*s*)*=(r+s)*由第一章的作業1.30中的第八題 (L2L1)*=( L2* L1*)* 其中L1、L2 為正則語言又r、s為正則表達式 正則語言可以用正則表達式表示，因此顯然有(r+s)*= (r*s*)*成立 即(r*s*)*=(r+s)*成立(11) (r*)*=r*由第一章的作業1.30中的第三題 (L1*)*= L1*其中L1為正則語言又r為正則表達式 正則語言可以用正則表"達式表示，因此顯然有(r*)*=

14、r*成立*4下面各式成立嗎？請證明你的結論(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時候，(r+rs)0 r=r= r(sr+r)0II. 假設k=n時候(r+rs)nr=r(sr+r)n成立，往證k=n+1時候結論成立 (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)=

15、 r(sr+r)n (sr+r)= r(sr+r)n+1這就是說，結論對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)*不成立，假設r,s分別是表示語言R，S的正則表達式，例如當R=0，S=1, L(s(rs+s)*r)是以1開

16、頭的字符串，而L(rr*s(rr*s)*)是以0開頭的字符串.L(s(rs+s)*r) L(rr*s(rr*s)*)所以s(rs+s)*r rr*s(rr*s)*,結論不成立(5)(r+s)*=(r*s*)*證明：結論成立。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

17、 ，所以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*不成立，假設r,s分別是表示語言R，S的正則表達式，例如當R=0，S=1,L(r+s)*)=x| x=或者x是所有由0,1組成的字符串L(r*+s*)=L(r*)L(s*)=,0,00,000,1,11,111,L(r+s)*) L(r*+s*),例如10 L(r+s)*),10 L(r*+s*)*5.構造下列正則表達式的等價FA 吳丹 02282090*6、構造等價于下圖所示DFA的

18、正則表達式。僅給出（2）的構造過程（1）與他等價的正則表達式為：+（01+1）（01+10+11（01+1）*Sq1q0q2q310001110（2）答案(之一)：( 01+(1+00)(1+00*1)0)*(1+00*1)1) )* (e+(1+00)(1+00*1)0)*00*)q1q0q2q310001110eeXYe預處理：去掉q3：q1q0q21011+00*10eXYe00*去掉q1：q0q21+00(1+00*1)0eXYe00*(1+00*1)101q0eXYe+(1+00)(1+00*1)0)*00*01+(1+00)(1+00*1)0)*(1+00*1)1)去掉q2：去掉q

19、0：XY(01+(1+00)(1+00*1)0)*(1+00*1)1)* (e+(1+00)(1+00*1)0)*00*)（3）（0+10）* 11）（01+(1+00）（0+10）* 11)*（0+（1+00）（0+10）*1）+（0+10）* 1(4）（0+11+10（0+1）（01）*+（00（0+1）*）*1）*（1+10+（0+11+10（0+1）（01）*+（00（0+1）*）*）（00+0+）*7.整理不同模型等價證明的思路 解：正則語言有5種等價的描述模型：正則文法（RG）、確定的有窮狀態自動機（DFA）、不確定的有窮狀態自動機（NFA）、帶空移動的有窮狀態自動機（）、正則表達式（RE）。這5種等價模型的轉換關系可以用下圖表示： （1）R