形式語言與自動(dòng)機(jī)理論-蔣宗禮-第四章參考答案

1.寫出表示以下語言的正那么表達(dá)式?！矃琴t珺02282047〕=1\*GB2⑴{0,1}*。解：所求正那么表達(dá)式為：(0+1)*。=2\*GB2⑵{0,1}+。解：所求正那么表達(dá)式為：(0+1)+。=3\*GB2⑶{x│x∈{0,1}+且x中不含形如00的子串}。解：根據(jù)第三章構(gòu)造的FA，可得所求正那么表達(dá)式為：1*(01+)*(01+0+1)。=4\*GB2⑷{x│x∈{0,1}*且x中不含形如00的子串}。解：根據(jù)上題的結(jié)果，可得所求正那么表達(dá)式為：ε+1*(01+)*(01+0+1)。=5\*GB2⑸{x│x∈{0,1}+且x中含形如10110的子串}。解：所求正那么表達(dá)式為：(0+1)*10110(0+1)*。=6\*GB2⑹{x│x∈{0,1}+且x中不含形如10110的子串}。解：根據(jù)第三章的習(xí)題，接受x的FA為：SS0110q0q1q2101110q3q4要求該FA對應(yīng)的正那么表達(dá)式，分別以q0、q1、q2、q3、q4為終結(jié)狀態(tài)考慮：q0為終態(tài)時(shí)的正那么表達(dá)式：(0*(11*0(10)*(ε+111*11*0(10)*)0)*)*q1為終態(tài)時(shí)的正那么表達(dá)式：0*1(1*(0(10)*111*1)*(0(10)*00*1)*)*q2為終態(tài)時(shí)的正那么表達(dá)式：0*11*0((10)*(111*11*0)*(00*11*0)*)*q3為終態(tài)時(shí)的正那么表達(dá)式：0*11*0(10)*1(11*11*0((10)*(00*11*0)*)*1)*q4為終態(tài)時(shí)的正那么表達(dá)式：0*11*0(10)*11(1*(11*0((00*11*0)*(10)*)*11)*)*將以上5個(gè)正那么表達(dá)式用“+〞號相連，就得到所要求的正那么表達(dá)式。=7\*GB2⑺{(lán)x│x∈{0,1}+且當(dāng)把x看成二進(jìn)制數(shù)時(shí)，x模5與3同余和x為0時(shí)，│x│=1且x≠0時(shí)，x的首字符為1}。解：先畫出狀態(tài)轉(zhuǎn)移圖，設(shè)置5個(gè)狀態(tài)q0、q1、q2、q3、q4，分別表示除5的余數(shù)是0、1、2、3、4的情形。另外，設(shè)置一個(gè)開始狀態(tài)q.由于要求x模5和3同余，而3模5余3,故只有q3可以作為終態(tài)。由題設(shè)，x=0時(shí)，│x│=1，模5是1，不符合條件，所以不必增加關(guān)于它的狀態(tài)。下面對每一個(gè)狀態(tài)考慮輸入0和1時(shí)的狀態(tài)轉(zhuǎn)移。 q:輸入1，模5是1，進(jìn)入q1。 q0:設(shè)x=5n。輸入0，x=5n*2=10n，模5是0，故進(jìn)入q0 輸入1，x=5n*2+1=10n+1，模5是1，故進(jìn)入q1 q1：設(shè)x=5n+1。輸入0，x=(5n+1)*2=10n+2，模5是2，故進(jìn)入q2 輸入1，x=(5n+1)*2+1=10n+3，模5是3，故進(jìn)入q3 q2：設(shè)x=5n+2。輸入0，x=(5n+2)*2=10n+4，模5是4，故進(jìn)入q4 輸入1，x=(5n+2)*2+1=10n+5，模5是0，故進(jìn)入q0 q3：設(shè)x=5n+3。輸入0，x=(5n+3)*2=10n+6，模5是1，故進(jìn)入q1 輸入1，x=(5n+3)*2+1=10n+7，模5是2，故進(jìn)入q2 q4：設(shè)x=5n+4。輸入0，x=(5n+4)*2=10n+8，模5是3，故進(jìn)入q3 輸入1，x=(5n+4)*2+1=10n+9，模5是4，故進(jìn)入q4那么狀態(tài)轉(zhuǎn)移圖如下：qq1q1S01q2q30q410101q001 那么所求的正那么表達(dá)式為：1(010*1+(1+001*0)(101*0)*(0+110*1))*(1+001*0)(101*0)* =8\*GB2⑻{x│x∈{0,1}+且x的第10個(gè)字符是1}。 解：所求正那么表達(dá)式為：(0+1)91(0+1)*。 =9\*GB2⑼{x│x∈{0,1}+且x以0開頭以1結(jié)尾}。 解：所求正那么表達(dá)式為：0(0+1)*1。=10\*GB2⑽{x│x∈{0,1}+且x中至少含兩個(gè)1}。 解：所求正那么表達(dá)式為：(0+1)*1(0+1)*1(0+1)*。=11\*GB2⑾{x│x∈{0,1}*和如果x以1結(jié)尾，那么它的長度為偶數(shù)；如果x以0結(jié)尾，那么它的長度為奇數(shù)}。 解：所求正那么表達(dá)式為：(0+1)2n+11+(0+1)2n0(n∈N)或0+(0+1)((0+1)(0+1))*1+(0+1)(0+1)((0+1)(0+1))*0。=12\*GB2⑿{x│x是十進(jìn)制非負(fù)實(shí)數(shù)}。解：首先定義∑＝{.,0,1,2,3,4,5,6,7,8,9} 那么所求正那么表達(dá)式為：(0+1+…+9)*.(0+1+…+9)*。=13\*GB2⒀Φ。 解：所求正那么表達(dá)式為：Φ。=14\*GB2⒁{ε}。 解：所求正那么表達(dá)式為：ε。*********************************************************************************2.理解如下正那么表達(dá)式，說明它們表示的語言〔1〕(00+11)+表示的語言特征是0和1都各自成對出現(xiàn)〔2〕(1+0)*0100+表示的語言特征是以010后接連續(xù)的0結(jié)尾〔3〕(1+01+001)*(+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é)尾的串*********************************************************************************************4.3.證明以下各式褚穎娜02282072〔1〕結(jié)合律(rs)t=r(st)(r+s)+t=r+(s+t)1〕證明對x∈(rs)t總可以找到一組x1x2x3使得x=x1x2x3其中x3∈tx1x2∈rs且x1∈r,x2∈s,那么x2x3∈st因此x1(x2x3)∈r(st)即x1x2x3∈r(st)x∈r(st)得證因此(rs)tr(st)同理可證r(st)(rs)t那么(rs)t=r(st)成立2)證明對x∈(r+s)+tx∈(r+s)或x∈t對于x∈r+sx∈r或r∈s，因此x∈r或x∈s或x∈tx∈r或x∈(s+t)x∈r+(s+t)所以(r+s)+tr+(s+t)同理可證r+(s+t)(r+s)+t那么(r+s)+t=r+(s+t)成立〔2〕分配律r(s+t)=rs+rt(s+t)r=sr+tr證明對于x∈r(s+t)總可以找到x1x2使得x=x1x2其中x1∈r,x2∈〔s+t〕由x2∈〔s+t〕x2∈s或x2∈t那么x1x2∈rs或x1x2∈rt所以r(s+t)rs+rt對于x∈rs+rtx∈rs或x∈rt且總可以找到一組x1x2使得x=x1x2其中x1∈r,x2∈s或x1∈r,x2∈tx1∈r，x2∈s或x2∈tx1∈r，x2∈(s+t)x1x2∈r(s+t)所以rs+rtr(s+t)那么r(s+t)=rs+rt證明對于x∈(s+t)r總可以找到x1x2使得x=x1x2其中x1∈〔s+t〕，x2∈r由x1∈〔s+t〕x1∈s或x1∈t那么x1x2∈sr或x1x2∈tr所以(s+t)rsr+tr對于x∈sr+trx∈sr或x∈tr且總可以找到一組x1x2使得x=x1x2其中x1∈s,x2∈r或x1∈t,x2∈rx1∈s或x1∈t,x2∈rx1∈(s+t),x2∈rx1x2∈(s+t)r所以sr+tr(s+t)r那么(s+t)r=sr+tr(3)交換律r+s=s+r證明對于x∈r+sx∈r或x∈sx∈s或x∈rx∈s+r所以r+ss+r同理可證s+r∈r+s那么r+s=s+r〔4〕冪等律r+r=r證明對于x∈r+rx∈r或x∈rx∈r所以r+rr對于x∈rx∈r或x∈rx∈r+r所以rr+r因此r+r=r〔5〕加法運(yùn)算零元素：r+=r證明對于x∈r+x∈r或x∈x∈r所以r+r對于x∈rx∈r或x∈x∈r+所以rr+因此r+=r(6)乘法運(yùn)算單位元：rε=εr=r證明：∵對xRx=x=x ∴R{}={}R=R ∴r=r=r(7)乘法運(yùn)算零元素：r=r=證明：∵對xRx=x= ∴R{}={}R=R ∴r=r=*=ε證明*=0∪1∪2∪3…...=ε∪1∪2∪3…...=ε(r+ε)*=r*由第一章的作業(yè)1.30中的第九題(L1∪{ε})*=L1*其中L1為正那么語言又r為正那么表達(dá)式正那么語言可以用正那么表達(dá)式表示，因此顯然有(r+ε)*=r*成立(r*s*)*=(r+s)*由第一章的作業(yè)1.30中的第八題(L2∪L1)*=(L2*L1*)*其中L1、L2為正那么語言又r、s為正那么表達(dá)式正那么語言可以用正那么表達(dá)式表示，因此顯然有(r+s)*=(r*s*)*成立即(r*s*)*=(r+s)*成立(r*)*=r*由第一章的作業(yè)1.30中的第三題(L1*)*=L1*其中L1為正那么語言又r為正那么表達(dá)式正那么語言可以用正那么表達(dá)式表示，因此顯然有(r*)*=r*成立*********************************************************************************4下面各式成立嗎？請證明你的結(jié)論(r+rs)*r=r(sr+r)*證明：成立。如果對所有的k>=0,(r+rs)kr=r(sr+r)k成立，那么(r+rs)*r=r(sr+r)*肯定成立可以用歸納法證明(r+rs)kr=r(sr+r)k對所有的k>=0成立I.k=0時(shí)候，(r+rs)0r=r=r(sr+r)0假設(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)nr(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)kr=r(sr+r)k對所有的k>=0成立，所以(r+rs)*r=r(sr+r)*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.rs=sr證明：不成立。不妨取r=0,s=1,顯然rs=01,而sr=10.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)*rrr*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}，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*),例如10L((r+s)*),10L(r*+s*)**********************************************************************************************吳丹02282090*********************************************************************************6、構(gòu)造等價(jià)于以下圖所示DFA的正那么表達(dá)式。僅給出〔2〕的構(gòu)造過程〔1〕與他等價(jià)的正那么表達(dá)式為：ε+〔01+1〕〔01+10+11〔01+1〕〕*SqSq1q0q2q310001110答案(之一)：(01+(1+00)((1+00*1)0)*((1+00*1)1))*(+(1+00)((1+00*1)0)*00*)qq1q0q2q310001110XY預(yù)處理：去掉q3：qq1q0q21011+00*10XY00*去掉q1：qq0q21+00(1+00*1)0XY00*(1+00*1)101q0XYq0XY+(1+00)((1+00*1)0)*00*01+(1+00)((1+00*1)0)*((1+00*1)1)去掉q0：XXY(01+(1+00)((1+00*1)0)*((1+00*1)1))*(+(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.整理不同模型等價(jià)證明的思路解：正那么語言有5種等價(jià)的描述模型：正那么文法〔RG〕、確定的有窮狀態(tài)自動(dòng)機(jī)〔DFA〕、不確定的有窮狀態(tài)自動(dòng)機(jī)〔NFA〕、帶空移動(dòng)的