自動(dòng)機(jī)理論、語言和計(jì)算導(dǎo)論課后習(xí)題答案(中文版)

SolutionsforSection2.2

Exercise2.2.1(a)

Statescorrespondtotheeightcombinationsofswitchpositions,andalso

mustindicatewhetherthepreviousrollcameoutatD,i.e.,whetherthe

previousinputwasaccepted.Let0representapositiontotheleft(as

inthediagram)and1apositiontotheright.Eachstatecanberepresented

byasequenceofthreeO'sor1's,representingthedirectionsofthethree

switches,inorderfromlefttoright.Wefollowthesethreebitsbyeither

aindicatingitisanacceptingstateorr,indicatingrejection.Ofthe

16possiblestates,itturnsoutthatonly13areaccessiblefromthe

initialstate,OOOr.Hereisthetransitiontable:

杠桿可能出現(xiàn)8種情況，影響著最終狀態(tài)。并且也要說明，前面一個(gè)大理石球是

否從D滾出，也就是說，前一個(gè)輸入是否被接受。令0代表向左方的狀態(tài)(如

圖表)，1代表向右方。這三個(gè)杠桿的每一個(gè)狀態(tài)都可以用三個(gè)數(shù)(0或1)組

成的序列表示。這個(gè)序列后面跟著字母a或者r。a代表接受狀態(tài)，r代表拒絕

狀態(tài)。16種可能的狀態(tài)中，只有13種是從初始狀態(tài)OOOr可達(dá)的。下面它的有

窮自動(dòng)機(jī)的轉(zhuǎn)移表。

AB

->000100)11

Vrr

100011

*000a

rr

101000

*00la

1ra

110001

010r

ra

110001

*010a

1ra

111010

Ollr

ra

010111

100r

rr

010111

*100a

rr

100

101r

a

可復(fù)制、編制，期待你的好評(píng)與關(guān)注!

Oil100

*101a

ra

000101

110r

aa

000101

*110a

aa

001110

lllr

aa

Exercise2.2.2

Thestatementtobeprovedis8-hat(q,xy)=8-hat(8-hat(q,x),y),and

weproceedbyinductiononthelengthofy.

證明：通過對(duì)Iy|進(jìn)行歸納，來證明“(q,xy)="("(q,x),y),具體過程

如下：

可復(fù)制、編制，期待你的好評(píng)與關(guān)注!

Basis:Ify=e,thenthestatementis5-hat(q,x)=

5-hat(5-hat(q,x),e).Thisstatementfollowsfromthebasisinthe

definitionof5-hat.Notethatinapplyingthisdefinition,wemusttreat

5-hat(q,x)asifitwerejustastate,sayp.Then,thestatementtobe

provedisp=8-hat(p,￡),whichiseasytorecognizeasthebasisin

thedefinitionof5-hat.

基礎(chǔ)：|y『0,則y=￡。那么需證"(q,x)二八(八(q,x),￡),記p=八(q,x),命題

變?yōu)閜二八(p,￡),由人的定義知這顯然成立。

Induction:Assumethestatementforstringsshorterthany,andbreaky

=za,whereaisthelastsymbolofy.Thestepsconverting

5-hat(5-hat(q,x),y)to5-hat(q,xy)aresummarizedinthefollowing

table:

歸納：假設(shè)命題對(duì)于比y短的串成立，且y二za,其中a是y的結(jié)尾符號(hào)。

八(八(q,x),y)到人(q,xy)的變換總結(jié)在下表中:

Expression表達(dá)

Reason原因

式

((q,x),y)Start開始

((q,x),za)y=zabyassumption由假設(shè)y=za

Definitionof6-hat,treating

6("("(q,x),z)8-hat(q,x)asastate

,a)”的定義，把"q,x)看作是一個(gè)狀態(tài)

S((q,xz),a)Inductivehypothesis歸納假設(shè)

(q,xza)Definitionof5-hat的定義

■，，

(q,xy)y=za

Exercise2.2.4(a)

可復(fù)制、編制，期待你的好評(píng)與關(guān)注!

TheintuitivemeaningsofstatesA,B,andCarethatthestringseenso

farendsin0,1,oratleast2zeros.

可復(fù)制、編制，期待你的好評(píng)與關(guān)注!

狀態(tài)A,B,C分別表示以1,0和00結(jié)尾的串的狀態(tài)。

01

->ABA

BcA

*CCA

Exercise2.2.6(a)

Thetrickistorealizethatreadinganotherbiteithermultipliesthe

numberseensofarby2(ifitisa0),ormultipliesby2andthenadds

1(ifitisa1).Wedon，tneedtoremembertheentirenumberseen—

justitsremainderwhendividedby5.Thatis,ifwehaveanynumberof

theform5a+b,wherebistheremainder,between0and4,then2(5a+b)

=10a+2b.Since10aissurelydivisibleby5,theremainderof10a+2bis

thesameastheremainderof2bwhendividedby5.Sinceb,is0,1,2,

3,or4,wecantabulatetheanswerseasily.Thesameideaholdsifwe

wanttoconsiderwhathappensto5a+bifwemultiplyby2andadd1.

對(duì)于一個(gè)二進(jìn)制整數(shù)，如果讀入一個(gè)比特0,其值等于原數(shù)乘以2；否則等

于原數(shù)乘以2再加以1。而任意一個(gè)數(shù)均可寫成形如5a+b,其中a任意，(K=b<=4,

那么輸入0,原數(shù)變?yōu)?(5a+b)=10a+2b,由于10a是5的倍數(shù)，，因此10a+2b

除以5的余數(shù)與2b相同。輸入1,則得2(5a+b)+l類似。因此對(duì)于所有的數(shù)只

要記住它被5除的余數(shù)就可以。由于b是0,1,2,3或者4,我們可以容易得

到該DPA的轉(zhuǎn)移表，具體如下：

Thetablebelowshowsthisautomaton.Stateqimeansthattheinputseen

sofarhasremainderiwhendividedby5.

其中狀態(tài)qi代表輸入串被5除的余數(shù)i的狀態(tài)。

Thereisasmallmatter,however,thatthisautomatonacceptsstringswith

leadingO's.Sincetheproblemcallsforacceptingonlythosestringsthat

beginwith1,weneedanadditionalstates,thestartstate,andan

additionaldeadstate，'d.If,instates,weseea1first,weactlike

可復(fù)制、編制，期待你的好評(píng)與關(guān)注!

qO;i.e.,wegotostateql.However,ifthefirstinputis0,weshould

neveraccept,sowegotostated,whichweneverleave.Thecomplete

automatonis:

可復(fù)制、編制，期待你的好評(píng)與關(guān)注!

但是上述自動(dòng)機(jī)仍接受以0開頭的字符串。因?yàn)轭}目要求只接受以1開頭的串,

可增加一個(gè)初始狀態(tài)s和“死亡狀態(tài)”d。在狀態(tài)初始狀態(tài)s,若看到1,則轉(zhuǎn)

到狀態(tài)ql;若看到0,則直接轉(zhuǎn)到狀態(tài)d,識(shí)別終止。所求自動(dòng)機(jī)如下：

01

->Sdqi

*q0q0qi

_qiq2q3

q2q4q0

q3qiq2

d-lq3q4

d3d

Exercise2.2.9

Part(a)isaneasyinductiononthelengthofw,startingatlength1.

Basis:|w|=1.Then8-hat(q,w)=8-hat(q,w),becausewisasingle

symbol,and8-hatagreeswith8onsinglesymbols.

Induction:Letw=za,sotheinductivehypothesisappliestoz.Then

5-hat(q,w)=5-hat(q,za)=5(8-hat(q,z),a)=8(8-hat(q,z),a)[by

.0o,0f

theinductivehypothesis]=5-hat(q,za)=o-hat(q,w).

ff

證明：a)通過對(duì)w長度的歸納證明。

基礎(chǔ)：若|w|=1,則w是一個(gè)符號(hào)，此時(shí)需證"(q,w)="(q,w),而對(duì)于單

0f

個(gè)符號(hào)擴(kuò)展轉(zhuǎn)移函數(shù)”與轉(zhuǎn)移函數(shù)5的作用是一樣的，得證。

歸納：令7=za,假設(shè)對(duì)于z命題(q,z)=(q,z)成立。那么(q,w)=

oro

八(q,za)=8("(q,z),a)=6("(q,z),a)[由歸納假設(shè)]="(q,za)：

00ff

?(q,w).

f

Forpart(b),weknowthat5-hat(q,x)=q.Sincex"weknowbypart

0f

(a)that8-hat(q,x)=q.Itisthenasimpleinductiononktoshowthat

8-hat(q,x。=q.

0f

Basis:Fork=lthestatementisgiven.

可復(fù)制、編制，期待你的好評(píng)與關(guān)注!

Induction:Assumethestatementfork-l;i.e.,8-hat(q,xSUP>k-l)=q.

0f

UsingExercise2.2.2,8-hat(q,xO=6-hat(5-hat(q,xk-i),x)=

5-hat(q,x)［bytheinductivehypothesis］=q［by(a)1.

ff

b)x是屬于L(A)的非空串，也即串x被接收，因此入(q,x)=q，則由a)知

0f

"(q,x)="(q,x)=q?，F(xiàn)在通過對(duì)k的歸納來證明”(q,X。=q。

fOf0f

基礎(chǔ)：k=l時(shí)，需證”(q,x)=q,由已知可得。

0f

歸納：假颯于kT命題啦也就是說"(q,xz)=q。由練習(xí)2.2.2,'(q,X。

0f0

='('(q,xT,x)="(q,x)［由歸納假設(shè)］=q［由(a)］。

0ff

Exercise2.2.10

Theautomatontellswhetherthenumberof1'sseeniseven(stateA)or

odd(stateB),acceptinginthelattercase.Itisaneasyinductionon

|w|toshowthatdh(A,w)=Aifandonlyifwhasanevennumberoffs.

Basis:|wj=0.Thenw,theemptystringsurelyhasanevennumberof1's,

namelyzerofs,and(A,w)=A.

Induction:Assumethestatementforstringsshorterthanw.Thenza,

whereaiseither0or1.

Case1:a=0.Ifwhasanevennumberof1's,sodoesz.Bytheinductive

hypothesis,(A,z)=A.ThetransitionsoftheDFAtellus(A,w)=

A.Ifwhasanoddnumberof1's,thensodoesz.Bytheinductivehypothesis,

5-hat(A,z)=B,andthetransitionsoftheDFAtellus-hat(A,w)5=B.

Thus,inthiscase,5-hat(A,w)=Aifandonlyifwhasanevennumber

ofrs.

Case2:a=1.Ifwhasanevennumberof1's,thenzhasanoddnumber

ofrs.Bytheinductivehypothesis,8-hat(A,z)=B.Thetransitionsof

theDFAtellus6-hat(A,w)=A.Ifwhasanoddnumberof1's,thenz

hasanevennumberofVs.Bytheinductivehypothesis,8-hat(A,z)=A,

andthetransitionsoftheDFAtellus5-hat(A,w)=B.Thus,inthiscase

aswell,8-hat(A,w)=Aifandonlyifwhasanevennumberof1's.

可復(fù)制、編制，期待你的好評(píng)與關(guān)注!

這個(gè)自動(dòng)機(jī)表示，狀態(tài)A表示偶數(shù)個(gè)1,狀態(tài)B表示奇數(shù)個(gè)1,不管串有偶數(shù)個(gè)

還是奇數(shù)個(gè)1,都會(huì)被接受。當(dāng)且僅當(dāng)串w中有偶數(shù)個(gè)1時(shí)，”(A,w)=A.o

用歸納法證明如下

基礎(chǔ)：同=Oo空串當(dāng)然有偶數(shù)個(gè)1,即。個(gè)1,且'(A,w)=A.

歸納：假設(shè)對(duì)于比w短的串命題成立。令w=za,其中a為0或1。

情形1：a=0.如果w有偶數(shù)個(gè)1,則z有偶數(shù)個(gè)1。由歸納假設(shè)，”(A,z)=

Ao由轉(zhuǎn)移表的DFA知"(A,w)=A.如果w有奇數(shù)個(gè)1,則z有奇數(shù)個(gè)1.由歸納

假設(shè)，'(A,z)=B,由轉(zhuǎn)移表的DFA知"(A,w)=B.因此這種情況下”(A,w)

=A當(dāng)且僅當(dāng)w有偶數(shù)個(gè)L

情形2：a=l.如果w有偶數(shù)個(gè)1,則z有奇數(shù)個(gè)1。由歸納假設(shè)，”(A,z)=

B.由轉(zhuǎn)移表的DFA知八(A,w)=A.如果w有奇數(shù)個(gè)1,則z有偶數(shù)個(gè)1。由

歸納假設(shè)，"(A,z)=A,由轉(zhuǎn)移表的DFA知"(A,w)=B.因此這種情況下

'(A,w)=A當(dāng)且僅當(dāng)w有偶數(shù)個(gè)1.

綜合上述情形，命題得證。

SolutionsforSection2.3

Exercise2.3.1

HerearethesetsofNFAstatesrepresentedbyeachoftheDFAstatesA

throughH:A={p};B={p,q};C={p,r};D={p,q,r};E={p,q,s};F=

{p,q,r,s};G={p,r,s};H={p,s}.

下表就是利用子集構(gòu)造法將NFA轉(zhuǎn)化成的DFA。其中構(gòu)造的子集有：A={p};B

={p,q};C={p,r};D={p,q,r};E={p,q,s};F={p,q,r,s};G={p,r,s};

H={p,s}.

可復(fù)制、編制，期待你的好評(píng)與關(guān)注!

可復(fù)制、編制，期待你的好評(píng)與關(guān)注!

Exercise2.3.4(a)

Theideaistouseastateqi,fori=0,1,...,9torepresenttheidea

thatwehaveseenaninputiandguessedthatthisistherepeateddigit

attheend.Wealsohavestateqs,theinitialstate,andqf,thefinal

state.Westayinstateqsallthetime;itrepresentsnoguesshaving

beenmade.Thetransitiontable:

記狀態(tài)qi為已經(jīng)看到i并猜測i就是結(jié)尾將要重復(fù)的數(shù)字，i=0,1,??.，9。

初始狀態(tài)為qs,終止?fàn)顟B(tài)為qf。我們可以一直停留在狀態(tài)qs,表示尚未猜測。

轉(zhuǎn)移表如下：

*

019

-〉q{qs,qO{qs,ql{qs,q9

S}})

q0{qf}{qO}{qO}

qi{ql}{qf}{ql}

????..?..,.?

q9{q9}{q9}{qf}

*qf0(){)

SolutionsforSection2.4

Exercise2.4.1(a)

可復(fù)制、編制，期待你的好評(píng)與關(guān)注!

We'11useqOasthestartstate,ql,q2,andq3willrecognizeabc;q4,

q5,andq6willrecognizeabd,andq7throughqlOwillrecognizeaacd.

Thetransitiontableis:

記qO為初始狀態(tài)。ql,q2和q3識(shí)另ijabc;q4,q5和q6識(shí)別abd,q7到qlO

識(shí)別aacd.轉(zhuǎn)移表如下：

可復(fù)制、編制，期待你的好評(píng)與關(guān)注!

{q2

ql期()()

)

{q3

q2()(){}

)

*q3()()()()

{q5

q4()(){)

)

q5n()0{q6}

*q6()()()(}

q7{q8}()()()

(q9

q8()(){)

)

{qlO

q9()()0

}

*qlOIT(}()()

Exercise2.4.2(a)

Thesubsetconstructiongivesusthefollowingstates,eachrepresenting

thesubsetoftheNFAstatesindicated:A={qO};B={qO,ql,q4,q7};C

={qO,ql,q4,q7,q8};D={qO,q2,q5};E={qO,q9};F={qO,q3};G={qO,q6};

H={qO,qlO}.NotethatF,GandHcanbecombinedintooneacceptingstate,

orwecanusethesethreestatetosignaltherecognitionofabc,abd,

andaacd,respectively.

由子集構(gòu)造法可得以下DFA的狀態(tài)，其中每一個(gè)狀態(tài)都是NFA狀態(tài)的子集：A=

{qO};B={qO,ql,q4,q7};C={qO,ql,q4,q7,q8};D={qO,q2,q5};E={qO,q9};

F={qO,q3};G={qO,q6};H={qO,qlO}.注意到F,G和H可以整合到一個(gè)

接受狀態(tài)中，或者我們可以用這三個(gè)狀態(tài)來分別標(biāo)記已識(shí)別abc,abd和aacd。

可復(fù)制、編制，期待你的好評(píng)與關(guān)注!

SolutionsforSection2.5

Exercise2.5.1

Forpart(a):theclosureofpisjust{p};forqitis{p,q},andfor

ritis{p,q,r}.

可復(fù)制、編制，期待你的好評(píng)與關(guān)注!

(a):根據(jù)狀態(tài)的e閉包的的性質(zhì)。求得，

P的￡閉包：{p};口的￡閉包：3,q};r的￡閉包：{p,q,r}。

For(b),beginbynoticingthataalwaysleavesthestateunchanged.Thus,

wecanthinkoftheeffectofstringsofb'sandcsonly.Tobegin,notice

thattheonlywaystogetfromptorforthefirsttime,usingonlyb,

c,and￡-transitionsarebb,be,andc.Aftergettingtor,wecanreturn

torreadingeitherborc.Thus,everystringoflength3orless,

consistingofb'sandcsonly,isaccepted,withtheexceptionofthe

stringb.However,wehavetoallowa'saswell.Whenwetrytoinsert

asinthesestrings,yetkeepingthelengthto3orless,wefindthat

everystringofa'sb's,andcswithatmostoneaisaccepted.Also,

thestringsconsistingofonecandupto2a'sareaccepted;otherstrings

arerejected.

b)由于輸入a狀態(tài)總是保持不變，因此只需考慮輸入b和c的情況。可以看出，

從狀態(tài)P第一次到r且只經(jīng)過b,c和e轉(zhuǎn)移的路徑為bb,13"和?；到r

之后，讀入b仍可回到r,讀入c回到p,則可通過繼續(xù)讀入串bb,be和c回

到ro

因此，每一個(gè)由b和c組成的長度小于等于3的串可以被接受，除了串b不能接

受。向這些串中插入a,并保持長度小于等于3,就會(huì)得到所有由a,b,c組成

的，至多含有一個(gè)a的可被接受的串。由一個(gè)c和兩個(gè)a組成的任意串也是可以

被接受的。其它的串均被拒絕。

TherearethreeDFAstatesaccessiblefromtheinitialstate,whichis

the￡closureofp,or{p}.LetA={p},B={p,q},andC={p,q,r}.Then

thetransitiontableis:

由初始優(yōu)杰，即p的￡閉包或者{p},有3個(gè)狀態(tài)可以達(dá)SU。令人={p},B={p,q},

C={p,q,r}o轉(zhuǎn)移表如下：

____

ablc

「AAB

3

*cCc

SolutionsforSection3.1

Exercise3.1.1(a)

Thesimplestapproachistoconsiderthosestringsinwhichthefirsta

precedesthefirstbseparatelyfromthosewheretheoppositeoccurs.The

可更制、編制，期待你的好評(píng)與關(guān)注!

expression:c*a(a+c)*b(a+b+c)*+c*b(b+c)*a(a+b+c)*

可復(fù)制、編制，期待你的好評(píng)與關(guān)注!

首先考慮第一個(gè)a在第一個(gè)b的前面，然后再考慮相反的情況。表達(dá)式為:

c*a(a+c)*b(a+b+c)*+c*b(b+c)*a(a+b+c)*

Exercise3.1.2(a)

(Revised9/5/05)Thetrickistostartbywritinganexpressionforthe

setofstringsthathavenotwoadjacent1's.Hereisonesuchexpression:

(10+0)*(e+l)

Toseewhythisexpressionworks,thefirstpartconsistsofallstrings

inwhichevery1isfollowedbya0.Tothat,wehaveonlytoaddthe

possibilitythatthereisa1attheend,whichwillnotbefollowedby

a0.Thatisthejobof(￡+1).

首先寫出沒有兩個(gè)1相鄰的串的集合，如下：(10+0)*(￡+1)。表達(dá)式的第一部

分表示每個(gè)1之后都緊跟一個(gè)0的這樣的串組成。為了表示結(jié)尾可能是1的情況，

則可在串尾處加上(￡+1)。

Now,wecanrethinkthequestionasaskingforstringsthathaveaprefix

withnoadjacent1'sfollowedbyasuffixwithnoadjacentO's.Theformer

istheexpressionwedeveloped,andthelatteristhesameexpression,

with0and1interchanged.Thus,asolutiontothisproblemis

(10+0)*(￡+1)(01+l)*(￡+0).Notethatthe￡+1terminthemiddleis

actuallyunnecessary,asa1matchingthatfactorcanbeobtainedfrom

the(01+1)*factorinstead.

題目要求的串可由兩部分組成，也就是，前綴沒有相鄰的1,后綴沒有相鄰的0。

前半部分也就是已經(jīng)給出的(10+0)*(￡+1),根據(jù)對(duì)稱性后半部分可將上式的1

和0交換得到。所求即為(10+0)*(￡+1)(01+1)*(￡+0)。注意中間的￡+1項(xiàng)沒

有作用，因?yàn)?可以由后面的(01+1)*項(xiàng)得到。因此最后得到的正則表達(dá)式為

(10+0)*(01+1)*(￡+0)

Exercise3.1.4(a)

Thisexpressionisanotherwaytowritenoadjacent1's.''Youshould

compareitwiththedifferent-lookingexpressionwedevelopedinthe

solutiontoExercise3.1.2(a).Theargumentforwhyitworksissimilar.

(00*1)*saysevery1isprecededbyatleastone0.0*attheendallows

0,safterthefinal1,and(e+1)atthebeginningallowsaninitial1,

whichmustbeeithertheonlysymbolofthestringorfollowedbya0.

你可以與練習(xí)3.1.2(a)中我們給出的不同樣子的表達(dá)式作比較。為什么起作用

的原因是類似的。

這個(gè)表達(dá)式是“沒有相鄰的1”的另一種描述方式。(00*1)*表示每個(gè)1的前

面都至少有一個(gè)0做前綴。最后的0*允許在最后一個(gè)1后面有0。開頭的

可復(fù)制、編制，期待你的好評(píng)與關(guān)注!

(￡+1)允許初始為1,要么串就只有這一個(gè)符號(hào)，要么后面跟著的就是0。

Exercise3.1.5

Thelanguageoftheregularexpression￡.Notethat￡*denotesthe

languageofstringsconsistingofanynumberofemptystrings,

concatenated,butthatisjustthesetcontainingtheemptystring.

正則表達(dá)式￡。￡*表示由任意多個(gè)空串組成的串，也是只包含空串的集合。

SolutionsforSection3.2

Exercise3.2.1

Part(a):ThefollowingareallR<>expressions;welistonlythesubscripts.

Rll=e+1;R12=0;R13=phi;R21=1;R22=e;R23=0;R31=phi;

R32=1;R33=￡+0.

a)下面就是所有Ro的表達(dá)式；我們只寫出下標(biāo)：R11=￡+1；R12=0;R13

=(phi);R21=1;R22=￡;R23=0;R31=(phi);R32=1;R33=e+0.

Part(b):HereallexpressionnamesareR<o;weagainlistonlythe

subscripts.Rll=1*;R12=1*0;R13=phi;R21=11*；R22=￡+11*0;R23

=0;R31=phi;R32=1;R33=e+0.

b)下面就是所有R<?的表達(dá)式；我們只寫出下標(biāo)：Rll=1*;R12=1*0;R13

=phi;R21=11*;R22=￡+11*0;R23=0;R31=phi;R32=1;R33=e+0.

Part(e):Hereisthetransitiondiagram轉(zhuǎn)移圖:

Ifweeliminatestateq2weget:

如果消除狀態(tài)q2,有：

H

可復(fù)制、編制，期待你的好評(píng)與關(guān)注!

Applyingtheformulainthetext,theexpressionforthewaystogetfrom

qltoq3is:[1+01+00(0+10)*111*00(0+10)*

由課本中的公式,ql到q3的正則表達(dá)式：[1+01+00(0+10)*111*00(0+10)*

Exercise3.2.4(a)

利用定理3O7每個(gè)用正則表達(dá)式來定義的語言也可用窮自動(dòng)機(jī)來定義

Exercise3.2.6(a)

(Revised修改1/16/02)LL*orL+.

Exercise3.2.6(b)

ThesetofsuffixesofstringsinL.(以)L中串(作為)后綴/下標(biāo)的集

人

口O

Exercise3.2.8

LetR(k)bethenumberofpathsfromstateitostatejoflengthmthat

ijm

gothroughnostatenumberedhigherthank.Wecancomputethesenumbers,

forallstatesiandj,andformnogreaterthann,byinductiononk.

令R&)為從狀態(tài)i到狀態(tài)j,長度為m,且沒有經(jīng)過編號(hào)大于k的路徑的個(gè)數(shù)。

對(duì)于質(zhì)看狀態(tài)I和j,以及m(n<n),通過對(duì)k歸納來計(jì)算這個(gè)個(gè)數(shù)。

Basis:Roisthenumberofarcs(ormoreprecisely,arclabels)fromstate

.ijl.,

itostatej.Ro=1,andallotherRosare0.

iiOijm

基礎(chǔ)：k=0,R。是由狀態(tài)i到狀態(tài)j的箭弧(更準(zhǔn)確的說，是箭弧標(biāo)號(hào))的個(gè)

數(shù)。R。=1,'箕他的心飛都為0。

iiOijm

Induction:R&)isthesumofR&Dandthesumoveralllists

,.ijmijm

(pl,p2,...,pr)ofpositiveintegersthatsumtom,ofD

ikplkkp2

*R(k-i)*...*R(k-i)*R(k-i).Notermustbeatleast2.

kkp3kkp(r-l)kjpr

歸納：R(k)是R(k-l)的和，R(k-l)*R(k-l)*R(k-l)*.?.*R(k-l)*R(k-l)

(pl,p2,.pr)是所％和為m的正磐數(shù)序列:i大于攀于2。如廣。汨

Theansweristhesumof初，wherekisthenumberofstates,1isthe

Ijn

startstate,andjisanyacceptingstate.

可復(fù)制、編制，期待你的好評(píng)與關(guān)注!

答案就是R<k)的總和，其中k是狀態(tài)個(gè)數(shù)，1為開始狀態(tài)，j是任意接受狀態(tài)。

Ijn

SolutionsforSection3.4

Exercise3.4.1(a)

ReplaceRby{a}andSby.Thentheleftandrightsidesbecome{a}

union=union{a}.Thatis,{a,b}={b,a}?Sinceorderisirrelevant

insets,bothlanguagesarethesame:thelanguageconsistingofthe

stringsaandb.

將R替換為{a},S替換為。等式變?yōu)棰?=+{a}.也就是{a,b}

={b,a}.因?yàn)榧现性氐捻樞蚴菬o關(guān)緊要的，所以，等式兩邊是一樣的：由

串a(chǎn)和b構(gòu)成的語言。

Exercise3.4.1(f)

ReplaceRby{a}.Therightsidebecomes{a}*,thatis,allstringsof

as,includingtheemptystring.Theleftsideis({a}*)*,thatis,all

stringsconsistingoftheconcatenationofstringsofa's.Butthatis

justthesetofstringsofa's,andisthereforeequaltotherightside.

將R替換為{a}。右邊變?yōu)閧a}*,代表a組成的所有串，包含空串。左邊是

({a}*)*,代表由a組成的串構(gòu)成的串，也就是由a構(gòu)成的串。當(dāng)然相等。

Exercise3.4.2(a)

Notthesame.ReplaceRby{a}andSby?Theleftsidebecomesall

stringsofa'sandb's(mixed),whiletherightsideconsistsonlyof

stringsofa's(alone)andstringsofb's(alone).Astringlikeabis

inthelanguageoftheleftsidebutnottheright.

不等。將R替換為{a},S替換為。左邊表示所有由a和b(可混合)構(gòu)成

的串。而右邊表示只有a構(gòu)成的串和只有b構(gòu)成的串。像ab這樣的串就只屬于

左邊的語言，而不屬于右邊。

Exercise3.4.2(c)

Alsonotthesame.ReplaceRby{a}andSby.Therightsideconsists

ofallstringscomposedofzeroormoreoccurrencesofstringsoftheform

a...ab,thatis,oneormorea，sendedbyoneb.However,everystring

inthelanguageoftheleftsidehastoendinab.Thus,forinstance,

eisinthelanguageontheright,butnotontheleft.

可復(fù)制、編制，期待你的好評(píng)與關(guān)注!

不等。舉反例，將R替換為｛a｝,S替換為｛b｝。右邊表示由0個(gè)或多個(gè)形如a...ab

組成的串，也就是，一個(gè)或多個(gè)a后面緊跟一個(gè)結(jié)尾的b。但是，左邊的串必須

以ab結(jié)尾。因此，￡屬于右邊的語言，但不屬于左邊。

SolutionsforSection4.1

Exercise4.1.1(c)

Letnbethepumping-lemmaconstant(notethisnisunrelatedtothen

thatisalocalvariableinthedef