形式语言与自动机理论-蒋宗礼-第三章参考答案

精品文档第三章作业答案M1与M218精品文档放心下载精品文档放心下载q0S0q1q00q1110101011100q2q32q3q10图qqqqqqqq;谢谢阅读03132313qqqqqqqq;精品文档放心下载02313231:精品文档放心下载谢谢阅读精品文档放心下载精品文档放心下载()精品文档放心下载*0，1+S00，11}且x00}谢谢阅读+00精品文档放心下载1。精品文档S110010,10{1}且x00}精品文档放心下载*S110010,101}且x10110}谢谢阅读+010,1S1011000

11}且x}感谢阅读+00精品文档放心下载1010,1S011001}且当把xx模5和3x为0且谢谢阅读+x0x1}以0感谢阅读设置7q,q除以5余0q5余1精品文档放心下载s：5余2q5余3q5余4q精品文档放心下载t01qqq012qqq132qqq204qqq3122。精品文档q4q3q4q00110qqqs12111q4000qt0,1q310且x1}谢谢阅读+x感谢阅读0,1S0,10,10,11感谢阅读0,1且x以01}谢谢阅读+1感谢阅读00S0110,11且x1}精品文档放心下载+3。精品文档00,111010x以1x以0感谢阅读+}1}4+q[：qx0qx1：qx0qx1q1q0001q4S011q3011q2}0S0，1，2，3，4，5，6，7，8，91，2，3，4，5，6，7，8，9.0，1，2，3，4，

5，6，7，8，9）S）S感谢阅读4。精品文档3）|x*}

|x}+）|xx00}感谢阅读+|xx00}谢谢阅读+|xx00}精品文档放心下载*|xx00}谢谢阅读*5。精品文档|xx{0}x100}精品文档放心下载**|xx1}谢谢阅读*|xx10}谢谢阅读*|xx101}精品文档放心下载*|xx1011}谢谢阅读*|xx10110}谢谢阅读*{}|x{0}}+|xxx1}感谢阅读*|xxx1}谢谢阅读*{}|xx感谢阅读+|xx感谢阅读+6。精品文档|xx谢谢阅读+|xx精品文档放心下载+|xx5=0x0}谢谢阅读+,0Q={q,q,q,q}012当(q,0)=(qi(q9(qq}i）{}

|x感谢阅读+|x谢谢阅读+|x精品文档放心下载+|x谢谢阅读+|x谢谢阅读+|x谢谢阅读+|x谢谢阅读+|x感谢阅读+|xx1}谢谢阅读+,0Q={q,q,q}01201q11q12q22q21q}2{}|x,并且x以0开头以0结尾}谢谢阅读+|x,并且x以0开头以1结尾}感谢阅读+,0Q={q,q,q}0120001q117。精品文档q12q22q22q}2|xx1}谢谢阅读+|xx1}谢谢阅读+,0Q={q,q,q,q,q}01234}20104q13q12q24q21q31q34q42q43q,q01{}|x,0}谢谢阅读+|x,1}谢谢阅读+|x,0}感谢阅读+|x,1}感谢阅读+,000,.12阅读感谢,.23文档放心下载精品4阅读{}感谢}}.}

}感谢阅读8。精品文档）{}

）{}精品文档放心下载4q[a...a]an12[a...a]an12q[a...a]an12）[aa12...an]q[aa12...an]q[aa12...an]感谢阅读FAFA感谢阅读谢谢阅读谢谢阅读FA）

解：⑴97FA精品文档放心下载感谢阅读谢谢阅读⑵精品文档放心下载谢谢阅读⑶谢谢阅读谢谢阅读感谢阅读精品文档放心下载x中0和1精品文档放心下载DFAMx1}且x+谢谢阅读中0的个数和1DFAM）

DFADFA精品文档放心下载感谢阅读感谢阅读DFA）精品文档放心下载9。精品文档S0AA|1

SB0S|0将1S,1代入S0A0S,0S得感谢阅读S|01S10S|10L={(10|01)},显然01或10谢谢阅读*中0和1精品文档放心下载,F)x,y,q(q,((q,x),y)

M=(Q,,,q感谢阅读0yx=0y=精品文档放心下载(q,)q,(q,xy)(q,x)((q,x),)((q,x),y),精品文档放心下载=n+1y===1感谢阅读谢谢阅读(q,xa)((q,xaa谢谢阅读(q,xy)(q,xwa)((q,xw),a)(((q,x),w),a)((q,x),wa)

((q,x),y)谢谢阅读y感谢阅读DFAMF)DFAMF),）谢谢阅读1122L(M)=Σ—LM*21M。2设MF)取MF)感谢阅读1121L(M)=Σ—M）*21xΣ*xL(MM）F）Q）FxΣ*2111xL(M)xM）11感谢阅读对于任意的M(Q,∑,δ,q,F),请构造M(Q,∑,δ,q,F)，使得谢谢阅读111222L(M)=L(M)L(M)={x|x）感谢阅读TTT12M取q,{q:精品文档放心下载10Q∪{q},qQ1001感谢阅读10。精品文档谢谢阅读1δ(q,ε)=F011T对q011aa…2ma1aa2ma…aa…a├qa├a122mmf1qqa…1a├a2m1aq…aqa22ma├2m1qq,a),q,a),q,a)并且q∈精品文档放心下载f01f1212mf精品文档放心下载F1则δ,a)=q,δ,aq,δ(q,a)=qδ(q,a)=q谢谢阅读1m11221111f感谢阅读因此qmama…aa├a1ma2qaq1faaaqaa├aaaqa├a21211…m2…1m因此am1aa)即x∈L(M)T111a…a∈L(M)xa2m1maa)1

1L(M)=L(M)T

1Mq,{qM=(,q,{q感谢阅读0320谢谢阅读^2NFAM=(,q,{q320感谢阅读M=(Q,∑,δ,F)Q=2F{q}精品文档放心下载Q11111δq…,q],a)=[p,p,p]当且仅当δ12n12nq…,qp,p}谢谢阅读22n12n谢谢阅读谢谢阅读）谢谢阅读(1){xx且x中不含形如的子串}谢谢阅读11。精品文档1S010111(2){xx且x中含形如10110的子串}谢谢阅读1011，10，1x且x10110的子串}感谢阅读1011，10，1(4){xx和x的倒数第个字符是，且以结尾}精品文档放心下载11111110111(5){xx且x以0开头以1结尾}精品文档放心下载0，101(6){xx且x}感谢阅读12欢迎下载。精品文档0，10，10，1S110，1(7){xx*且如果x以1感谢阅读如果以0}1S10x且x的首字符和尾字符相等}谢谢阅读01001111(9){xxTx,}0,100110,1精品文档放心下载感谢阅读）谢谢阅读13欢迎下载。精品文档）M1012精品文档放心下载}{q0}谢谢阅读012

感谢阅读精品文档放心下载谢谢阅读精品文档放心下载感谢阅读精品文档放心下载精品文档放心下载q0[q0,q1]0[q0,q1,q3][q0,q2,q3]0101,21,2[q0,q2]22[q0,q1,q2]2100,10,1[q0,q1,q2,q3]2图3-9NFAM2012}精品文档放心下载14。精品文档}}{012谢谢阅读感谢阅读谢谢阅读精品文档放心下载谢谢阅读q0201[q0,q1,q2]1[q1,q3]0211[q1,q2]0220100[q2]2[q2,q3][q1]01[q3,q1,q2]201图3-10NFA谢谢阅读NFA感谢阅读）NFAM=(Q的谢谢阅读NFANFA感谢阅读15。精品文档NFA与

原NFA感谢阅读精品文档放心下载该感谢阅读谢谢阅读13．试给出一个构造方法，对于任意的M1M)(Q,,,q,F)L(M*L(M)2220221(Q,,1,q10,F)，构造1DFA8谢谢阅读NFAM，M)L(M)11L(M3

3M(Q,,,[q],F),33330Q2,F{[p,p...p]|{p,...p}Q,{p,},{p,...3312pp...p}Fpm1m1

mQ22

12

1([q...q],a)[p...p]...q},a)31{p...p}1nm111nm在，QQ,F{[p...p]|[p...p]F223}2,211此mm基

础

上33MM确定化后不是终结状态的状态为M,,,q12

4)L(M*L(M)M(QM23344中QQ,,F43434Q4M1L(M)*,4xL(M),则(q,x)F(q,x)FxL(M20203)*,故x),又因为3*L(M)，3(q,x)Q(q,x)F(q,x)L(M030404故L(M)*L(M)23L(M)*L(M)23故L(M2)*)L(M)，L(M3L(M3)，)*2L(M)故1L(M1M2感谢阅读16欢迎下载。精品文档。精品文档放心下载⑴{且x和x++01。感谢阅读1111110,1101精品文档放心下载ε

ε11S10110εε⑵{x10110}{x10精品文档放心下载++01结尾}11S101101ε1110,111101谢谢阅读⑶{且x且x以01++。谢谢阅读5精品文档放心下载q00谢谢阅读q:q12个以上的0后输入110精品文档放心下载q:表示q02个以上的01021精品文档放心下载q:表示q12010132谢谢阅读q:表示q12个以上的0101143谢谢阅读17。精品文档011εεq01011qqq0213q410εεSεεε1F01εs0s12⑷{且x00x11的感谢阅读++。0S1001ε11011DFAqt18。精品文档0Sq0101q4q21q11q60q50qt0q1131001⑸{且x00且x11谢谢阅读++串。x0011x01谢谢阅读ε01εεSεεεε10εq谢谢阅读+01S00,1011qt0101感谢阅读的状态转移函数，起始状态q的q={qq}。谢谢阅读3002）感谢阅读19。精品文档01{qq}{qqq}{qqqq}2，2，，3{qqq}{qqqq}{qqqq}，2，，3，，3{qqqq}{qqqq}{qqqq}，，3，，3，，3q{qq{qqq}q{qqqq}qq{q2，2，，33qqq}，，301S0010q1q201{qq}{qq}{qqqq}3，2，，3{qq}{qq}{qqq}，2，2，3{qqqq}{qqq}{qqqq}，，3，，3，，3{qqq}{qqq}{qqqq}，3，，3，，3{qqq}{qq}{qqqq}，，3，2，，3q{qq{qq}q{qqqq}q{qqq}q{qqq}3，2，，3，3，，3qqqq,q，，34S1q201q000q111q30q4到DFA到NFA-NFA精品文档放心下载）01q(){qqqq}{qqqq}0，23，，3q{qqqq}{qqq}1，，3，，3q{qqqq}qq}2，，3，，3q{qqqq}{qqqq}3，，3，，301q(){qqq}{qqqq}012，，，3q{q}{qq}12，2q{qq}{qqq}2，，3，320。精品文档q空{q30}精品文档放心下载的FAM(Q,∑,δ,q,F)M(Q,∑,δ,q,F)，精品文档放心下载11112222谢谢阅读L(M)∪L(M)）感谢阅读12Q1与Q空2）构造Q∪Q∪{qq,F感谢阅读120012F∪F12q0}112a)=δ2L(M12设x∈L(M)∪L(Mxxx时感谢阅读12121δ(q11由Mq,xq000,,=δ1,,1,即x∈L(M2故L(M12)12设则q,x0由Mq,xq000},x),,,因为Q1与Qq,xF∪F2012则,δ(q,11x∈L(M)121。精品文档,因为Q1与Qq,xF∪F2012则,δ(q,21x∈L(M)2x∈L(M)∪L(M)谢谢阅读1212L(M)=)12精品文档放心下载）FAM1(Q,,111存在FAM,L(M)L(M12,q,),FFAM2(Q,21).,2,q,F),22M(Q,,,q,{f})δ谢谢阅读Q122对-{f}11；对-{f}22a)=δ；2δ(f}1L(M)L(M)L(M)，)12L(M)L(M)L(M)L(M)L(M2L(M)121L(M)L(M)12L(M)设x),从而有xL(M并且L(M)L(M2xL(M),11122使得xxx12M在处理x的过程中,经过的状态全部都是Q,所以在定义111感谢阅读M,对qQ,a,(q,x)(q,a)精品文档放心下载11故(q,x)(q,x){f}感谢阅读01110121M在处理x,经过的状态全部都是Q,义222精品文档放心下载M,对qQ,a,(q,x)(q,a)精品文档放心下载12(q,x)(q,x){f}谢谢阅读0222xL(M)(q,x)(q,x)x01011

2((q,x),x)0112((q,x),x)10112(f,x)12(f,x)12((f,),x)12(q,x)022(q,x)2022{f}2即得证xL(M)22。精品文档L(M)L(M)L(M1设xL(M),即2)(q,x){f}012由于M是从q由M,M要达到状态f,谢谢阅读012先到f由于除了对应状态转移函数式(f,)的移动感谢阅读1102,不存在从f,而且该移动是f谢谢阅读12,所以比存在x的前缀x和后缀x,xxx,x感谢阅读12121将M从状态q引导到状态f,x将M从状态q引导到状态f谢谢阅读0112022即(q,x))

(q,xx010112(f,x)12其中,(f,x)12(q,x)022{f}2(q,x){f},说明(q,x){f};感谢阅读011110111(q,x){f},说明(q,x){f}精品文档放心下载0222222这表明xL(M)11xL(M)22从而xxL(M)L(M)x1212故L(M)L(M)L(M)12综上所述,L(M)L(M)L(M2

1感谢阅读）23欢迎下载。精品文档＝Q，FAM＝Q18.证明：对于任意的FAMqFqF1，，，01，122，，2，，2存在FA，使得LM＝LMLM。12证明：不妨将这些看成DFA取M＝QFQ，q，q121201对于a.，q,pq,p，a＝q，a，p，a1212xx1x2......xk其中xik1设：xLM则i1,12使得q,p，xiq，xi,p，xi12xiLMLMxLMLM1212从而可得LMLMLM12xx1x2......xk其中xik2设：xLMLM则i1,1212有q，xi且p，xi从而使得12xi＝q,p，xi；xi＝q,p，xi12xiLMxLM从而可得LMLMLM12综合(1)(2)可得LM＝LMLM。12又因为和具有等价性，所以原命题得证。感谢阅读）谢谢阅读和谢谢阅读FAq）精品文档放心下载0δ感谢阅读ε谢谢阅读谢谢阅读）

DFA谢谢阅读感谢阅读谢谢阅读与2DFA与NFA感谢阅读谢谢阅读203-20DFA精品文档放心下载24。精品文档S0A|1|1C

A0S：|1|1CB0||1SC0A|1AS0A|1B

A|1|：0BB|0

|1AC0A|1A精品文档放心下载DFA精品文档放心下载⑴0q0q1S0111

1q20q3解：设qq、qq。感谢阅读0123由于q精品文档放心下载2⑵Sq001q110110q

1230感谢阅读25。精品文档qqqq。谢谢阅读0123谢谢阅读。）感谢阅读:a,cSaAaabZa,b,cBa,b,ca,cZaAaabSB谢谢阅读26。精品文档M:）精品文档放心下载δ(q,3)={q}00δ(q,1)={q}01δ(q,0)={q}12δ(q,1)={q}13δ(q,0)={q}22δ(q,1)={q}33,q,q.23(1)M是DFA?.

DFA谢谢阅读q130

1103qq01q302q1DFAq的Σ且δ(q,x)=q}谢谢阅读*0set(q)={3}*0set(q)={31}*1set(q)={3100}**

2set(q)={3111}**

330|313|3100(1|3)|3111013}感谢阅读********使q→3q|1q001q→0q|1q123qq22qq33感谢阅读FA）精品文档放心下载a1a2anaa感谢阅读n精品文档放心下载anFAAaB精品文档放心下载AaAa

。感谢阅读27。精品文档ana感谢阅读n感谢阅读aanFAABAa。谢谢阅读谢谢阅读FA）精品文档放心下载M,F)(Q,,,q0Aa的产生式，增加一个开始状态Z，使得q0ZE=F,对于产生式BAa,则有(A,a)B,感谢阅读对于产生式Ba,且E是开始状态，则有(E,a)与FA谢谢阅读M(Q,,,q0,F)做谢谢阅读删除FA在FA感谢阅读(A,a)B，则有产生式Ba精品文档放心下载(A,a)B,且A是开始状态q0,则有产生式Ba。谢谢阅读）28。精品文档26.2与FA2MM＝Q，，，q，F谢谢阅读0Q，，q，F。0：QQL，R，Sq，aQ，精品文档放心下载1q，a＝p，Laqp精品文档放心下载2q，a＝p，Raqp感谢阅读3q，a＝p，Saqp精品文档放心下载谢谢阅读感谢阅读FAqQ,a谢谢阅读(q,a){(p,D)...(p1m,D)}D的2NFA精品文档放心下载M1(Q,,,F,q1110M,,,F,q)2(Q220220等2,q)，,,1(Q,,,2(Q20构造M的F2111M),F2,q)，0按三个方式构造：2