自动机理论、语言和计算导论课后习题答案(中文版)

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:

杠杆可能出现8种情况，影响着最终状态。并且也要说明，前面一个大理石球是

否从D滚出，也就是说，前一个输入是否被接受。令0代表向左方的状态(如

图表)，1代表向右方。这三个杠杆的每一个状态都可以用三个数(0或1)组

成的序列表示。这个序列后面跟着字母a或者r。a代表接受状态，r代表拒绝

状态。16种可能的状态中，只有13种是从初始状态OOOr可达的。下面它的有

穷自动机的转移表。

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

可复制、编制，期待你的好评与关注!

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.

证明：通过对Iy|进行归纳，来证明“(q,xy)="("(q,x),y),具体过程

如下：

可复制、编制，期待你的好评与关注!

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.

基础：|y『0,则y=£。那么需证"(q,x)二八(八(q,x),£),记p=八(q,x),命题

变为p二八(p,£),由人的定义知这显然成立。

Induction:Assumethestatementforstringsshorterthany,andbreaky

=za,whereaisthelastsymbolofy.Thestepsconverting

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

table:

归纳：假设命题对于比y短的串成立，且y二za,其中a是y的结尾符号。

八(八(q,x),y)到人(q,xy)的变换总结在下表中:

Expression表达

Reason原因

式

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

((q,x),za)y=zabyassumption由假设y=za

Definitionof6-hat,treating

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

,a)”的定义，把"q,x)看作是一个状态

S((q,xz),a)Inductivehypothesis归纳假设

(q,xza)Definitionof5-hat的定义

■，，

(q,xy)y=za

Exercise2.2.4(a)

可复制、编制，期待你的好评与关注!

TheintuitivemeaningsofstatesA,B,andCarethatthestringseenso

farendsin0,1,oratleast2zeros.

可复制、编制，期待你的好评与关注!

状态A,B,C分别表示以1,0和00结尾的串的状态。

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.

对于一个二进制整数，如果读入一个比特0,其值等于原数乘以2；否则等

于原数乘以2再加以1。而任意一个数均可写成形如5a+b,其中a任意，(K=b<=4,

那么输入0,原数变为2(5a+b)=10a+2b,由于10a是5的倍数，，因此10a+2b

除以5的余数与2b相同。输入1,则得2(5a+b)+l类似。因此对于所有的数只

要记住它被5除的余数就可以。由于b是0,1,2,3或者4,我们可以容易得

到该DPA的转移表，具体如下：

Thetablebelowshowsthisautomaton.Stateqimeansthattheinputseen

sofarhasremainderiwhendividedby5.

其中状态qi代表输入串被5除的余数i的状态。

Thereisasmallmatter,however,thatthisautomatonacceptsstringswith

leadingO's.Sincetheproblemcallsforacceptingonlythosestringsthat

beginwith1,weneedanadditionalstates,thestartstate,andan

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

可复制、编制，期待你的好评与关注!

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

neveraccept,sowegotostated,whichweneverleave.Thecomplete

automatonis:

可复制、编制，期待你的好评与关注!

但是上述自动机仍接受以0开头的字符串。因为题目要求只接受以1开头的串,

可增加一个初始状态s和“死亡状态”d。在状态初始状态s,若看到1,则转

到状态ql;若看到0,则直接转到状态d,识别终止。所求自动机如下：

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)通过对w长度的归纳证明。

基础：若|w|=1,则w是一个符号，此时需证"(q,w)="(q,w),而对于单

0f

个符号扩展转移函数”与转移函数5的作用是一样的，得证。

归纳：令7=za,假设对于z命题(q,z)=(q,z)成立。那么(q,w)=

oro

八(q,za)=8("(q,z),a)=6("(q,z),a)[由归纳假设]="(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.

可复制、编制，期待你的好评与关注!

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。现在通过对k的归纳来证明”(q,X。=q。

fOf0f

基础：k=l时，需证”(q,x)=q,由已知可得。

0f

归纳：假飒于kT命题啦也就是说"(q,xz)=q。由练习2.2.2,'(q,X。

0f0

='('(q,xT,x)="(q,x)［由归纳假设］=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.

可复制、编制，期待你的好评与关注!

这个自动机表示，状态A表示偶数个1,状态B表示奇数个1,不管串有偶数个

还是奇数个1,都会被接受。当且仅当串w中有偶数个1时，”(A,w)=A.o

用归纳法证明如下

基础：同=Oo空串当然有偶数个1,即。个1,且'(A,w)=A.

归纳：假设对于比w短的串命题成立。令w=za,其中a为0或1。

情形1：a=0.如果w有偶数个1,则z有偶数个1。由归纳假设，”(A,z)=

Ao由转移表的DFA知"(A,w)=A.如果w有奇数个1,则z有奇数个1.由归纳

假设，'(A,z)=B,由转移表的DFA知"(A,w)=B.因此这种情况下”(A,w)

=A当且仅当w有偶数个L

情形2：a=l.如果w有偶数个1,则z有奇数个1。由归纳假设，”(A,z)=

B.由转移表的DFA知八(A,w)=A.如果w有奇数个1,则z有偶数个1。由

归纳假设，"(A,z)=A,由转移表的DFA知"(A,w)=B.因此这种情况下

'(A,w)=A当且仅当w有偶数个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}.

下表就是利用子集构造法将NFA转化成的DFA。其中构造的子集有：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}.

可复制、编制，期待你的好评与关注!

可复制、编制，期待你的好评与关注!

Exercise2.3.4(a)

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

thatwehaveseenaninputiandguessedthatthisistherepeateddigit

attheend.Wealsohavestateqs,theinitialstate,andqf,thefinal

state.Westayinstateqsallthetime;itrepresentsnoguesshaving

beenmade.Thetransitiontable:

记状态qi为已经看到i并猜测i就是结尾将要重复的数字，i=0,1,・・.，9。

初始状态为qs,终止状态为qf。我们可以一直停留在状态qs,表示尚未猜测。

转移表如下：

*

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)

可复制、编制，期待你的好评与关注!

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

q5,andq6willrecognizeabd,andq7throughqlOwillrecognizeaacd.

Thetransitiontableis:

记qO为初始状态。ql,q2和q3识另ijabc;q4,q5和q6识别abd,q7到qlO

识别aacd.转移表如下：

可复制、编制，期待你的好评与关注!

{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.

由子集构造法可得以下DFA的状态，其中每一个状态都是NFA状态的子集：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可以整合到一个

接受状态中，或者我们可以用这三个状态来分别标记已识别abc,abd和aacd。

可复制、编制，期待你的好评与关注!

SolutionsforSection2.5

Exercise2.5.1

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

ritis{p,q,r}.

可复制、编制，期待你的好评与关注!

(a):根据状态的e闭包的的性质。求得，

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状态总是保持不变，因此只需考虑输入b和c的情况。可以看出，

从状态P第一次到r且只经过b,c和e转移的路径为bb,13"和©；到r

之后，读入b仍可回到r,读入c回到p,则可通过继续读入串bb,be和c回

到ro

因此，每一个由b和c组成的长度小于等于3的串可以被接受，除了串b不能接

受。向这些串中插入a,并保持长度小于等于3,就会得到所有由a,b,c组成

的，至多含有一个a的可被接受的串。由一个c和两个a组成的任意串也是可以

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

TherearethreeDFAstatesaccessiblefromtheinitialstate,whichis

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

thetransitiontableis:

由初始优杰，即p的£闭包或者{p},有3个状态可以达SU。令人={p},B={p,q},

C={p,q,r}o转移表如下：

____

ablc

「AAB

3

*cCc

SolutionsforSection3.1

Exercise3.1.1(a)

Thesimplestapproachistoconsiderthosestringsinwhichthefirsta

precedesthefirstbseparatelyfromthosewheretheoppositeoccurs.The

可更制、编制，期待你的好评与关注!

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

可复制、编制，期待你的好评与关注!

首先考虑第一个a在第一个b的前面，然后再考虑相反的情况。表达式为:

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).

首先写出没有两个1相邻的串的集合，如下：(10+0)*(£+1)。表达式的第一部

分表示每个1之后都紧跟一个0的这样的串组成。为了表示结尾可能是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。

前半部分也就是已经给出的(10+0)*(£+1),根据对称性后半部分可将上式的1

和0交换得到。所求即为(10+0)*(£+1)(01+1)*(£+0)。注意中间的£+1项没

有作用，因为1可以由后面的(01+1)*项得到。因此最后得到的正则表达式为

(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.

你可以与练习3.1.2(a)中我们给出的不同样子的表达式作比较。为什么起作用

的原因是类似的。

这个表达式是“没有相邻的1”的另一种描述方式。(00*1)*表示每个1的前

面都至少有一个0做前缀。最后的0*允许在最后一个1后面有0。开头的

可复制、编制，期待你的好评与关注!

(£+1)允许初始为1,要么串就只有这一个符号，要么后面跟着的就是0。

Exercise3.1.5

Thelanguageoftheregularexpression£.Notethat£*denotesthe

languageofstringsconsistingofanynumberofemptystrings,

concatenated,butthatisjustthesetcontainingtheemptystring.

正则表达式£。£*表示由任意多个空串组成的串，也是只包含空串的集合。

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的表达式；我们只写出下标：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<»的表达式；我们只写出下标：Rll=1*;R12=1*0;R13

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

Part(e):Hereisthetransitiondiagram转移图:

Ifweeliminatestateq2weget:

如果消除状态q2,有：

H

可复制、编制，期待你的好评与关注!

Applyingtheformulainthetext,theexpressionforthewaystogetfrom

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

由课本中的公式,ql到q3的正则表达式：[1+01+00(0+10)*111*00(0+10)*

Exercise3.2.4(a)

利用定理3O7每个用正则表达式来定义的语言也可用穷自动机来定义

Exercise3.2.6(a)

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

Exercise3.2.6(b)

ThesetofsuffixesofstringsinL.(以)L中串(作为)后缀/下标的集

人

口O

Exercise3.2.8

LetR(k)bethenumberofpathsfromstateitostatejoflengthmthat

ijm

gothroughnostatenumberedhigherthank.Wecancomputethesenumbers,

forallstatesiandj,andformnogreaterthann,byinductiononk.

令R&)为从状态i到状态j,长度为m,且没有经过编号大于k的路径的个数。

对于质看状态I和j,以及m(n<n),通过对k归纳来计算这个个数。

Basis:Roisthenumberofarcs(ormoreprecisely,arclabels)fromstate

.ijl.,

itostatej.Ro=1,andallotherRosare0.

iiOijm

基础：k=0,R。是由状态i到状态j的箭弧(更准确的说，是箭弧标号)的个

数。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的正磐数序列:i大于攀于2。如广。汨

Theansweristhesumof初，wherekisthenumberofstates,1isthe

Ijn

startstate,andjisanyacceptingstate.

可复制、编制，期待你的好评与关注!

答案就是R<k)的总和，其中k是状态个数，1为开始状态，j是任意接受状态。

Ijn

SolutionsforSection3.4

Exercise3.4.1(a)

ReplaceRby{a}andSby{b}.Thentheleftandrightsidesbecome{a}

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

insets,bothlanguagesarethesame:thelanguageconsistingofthe

stringsaandb.

将R替换为{a},S替换为{b}。等式变为⑸+{b}={b}+{a}.也就是{a,b}

={b,a}.因为集合中元素的顺序是无关紧要的，所以，等式两边是一样的：由

串a和b构成的语言。

Exercise3.4.1(f)

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

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

stringsconsistingoftheconcatenationofstringsofa's.Butthatis

justthesetofstringsofa's,andisthereforeequaltotherightside.

将R替换为{a}。右边变为{a}*,代表a组成的所有串，包含空串。左边是

({a}*)*,代表由a组成的串构成的串，也就是由a构成的串。当然相等。

Exercise3.4.2(a)

Notthesame.ReplaceRby{a}andSby{b}・Theleftsidebecomesall

stringsofa'sandb's(mixed),whiletherightsideconsistsonlyof

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

inthelanguageoftheleftsidebutnottheright.

不等。将R替换为{a},S替换为{b}。左边表示所有由a和b(可混合)构成

的串。而右边表示只有a构成的串和只有b构成的串。像ab这样的串就只属于

左边的语言，而不属于右边。

Exercise3.4.2(c)

Alsonotthesame.ReplaceRby{a}andSby{b}.Therightsideconsists

ofallstringscomposedofzeroormoreoccurrencesofstringsoftheform

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

inthelanguageoftheleftsidehastoendinab.Thus,forinstance,

eisinthelanguageontheright,butnotontheleft.

可复制、编制，期待你的好评与关注!

不等。举反例，将R替换为｛a｝,S替换为｛b｝。右边表示由0个或多个形如a...ab

组成的串，也就是，一个或多个a后面紧跟一个结尾的b。但是，左边的串必须

以ab结尾。因此，£属于右边的语言，但不属于左边。

SolutionsforSection4.1

Exercise4.1.1(c)

Letnbethepumping-lemmaconstant(notethisnisunrelatedtothen

thatisalocalvariableinthedef