課后作業(yè)講解付國(guó)宏黑龍江大學(xué)計(jì)算機(jī)科學(xué)技術(shù)學(xué)院

ghfu@形式語(yǔ)言與自動(dòng)機(jī)理論/10/101(C)GuohongFu,CS@HLJU第1頁(yè)課后作業(yè)作業(yè)一：pp.39-41習(xí)題21,22,23,28(1)(2)(10)作業(yè)二：pp.83-85習(xí)題7(1),8(3),9(2)作業(yè)三：pp.126-130習(xí)題1,2(3)(5),7作業(yè)四：pp.128-129習(xí)題11(1),15(1)作業(yè)五：pp.129-130習(xí)題20,21,

22

作業(yè)六：pp.153-155習(xí)題1(5),2(2),5(2),

6(圖4-24)作業(yè)七：pp.191習(xí)題2(1)(2)

作業(yè)八：pp.230習(xí)題11(1),12(2)

作業(yè)九：pp.233習(xí)題15

作業(yè)十：pp.257-258習(xí)題1(1),8(1)GHF/10/102(C)GuohongFu,CS@HLJU第2頁(yè)課后作業(yè)一pp.39-41：L基本概念習(xí)題21---字母表習(xí)題22---前/后綴習(xí)題23---前/后綴習(xí)題28(1)(2)(10)---L描述GHF/10/103(C)GuohongFu,CS@HLJU第3頁(yè)課后作業(yè)一(cont.)pp.40：習(xí)題21判斷集合是否字母表依據(jù)非空性有窮性可區(qū)分性：字母表中字符兩兩互不相同整體性或不可分性解答：(1)、(2)和(6)是字母表，其它不是(3)?---不滿足非空性(4){a,b,a,c}---不滿足可區(qū)分性(5){0,1,2,…,n,…}---不滿足有窮性GHF/10/104(C)GuohongFu,CS@HLJU第4頁(yè)課后作業(yè)一(cont.)pp.40：習(xí)題22解答前綴：{,a,aa,aaa,aaaa,aaaaa,aaaaab,aaaaabb,aaaaabbb,aaaaabbbb,aaaaabbbba}真前綴：{,a,aa,aaa,aaaa,aaaaa,aaaaab,aaaaabb,aaaaabbb,aaaaabbbb}后綴：{,a,ba,bba,bbba,bbbba,abbbba,aabbbba,aaabbbba,aaaabbbba,aaaaabbbba}真后綴：{,a,ba,bba,bbba,bbbba,abbbba,aabbbba,aaabbbba,aaaabbbba}GHF/10/105(C)GuohongFu,CS@HLJU第5頁(yè)課后作業(yè)一(cont.)pp.40：習(xí)題23解答前綴：{,aa,aaaa,aaaaab,aaaaabbb,aaaaabbbba}真前綴：{,aa,aaaa,aaaaab,aaaaabbb}后綴：{,ba,bbba,abbbba,aaabbbba,aaaaabbbba}真后綴：{,ba,bbba,abbbba,aaabbbba}注意是任何串前綴、真前綴、后綴和真后綴；任何串是本身前綴和后綴，但不是本身真前綴和真后綴；注意字母表中字符整體性。GHF/10/106(C)GuohongFu,CS@HLJU第6頁(yè)課后作業(yè)一(cont.)pp.40：習(xí)題28(1)(2)(10)(1)L1={0n1n|n1}---表示0和1個(gè)數(shù)相同，且全部0位于1之前，長(zhǎng)度大于10、1串集合(2)L2={0n1m|n,m1}

---表示全部0位于1之前，長(zhǎng)度大于10、1串集合(10)L10={0,1,00,01,10,11,000,…}

---表示長(zhǎng)度大于00、1串集合GHF/10/107(C)GuohongFu,CS@HLJU第7頁(yè)課后作業(yè)二pp.83-85---LG習(xí)題7(1)---GL習(xí)題8(3)---LG習(xí)題9(2)---LGGHF/10/108(C)GuohongFu,CS@HLJU第8頁(yè)課后作業(yè)二(cont.)pp.84：習(xí)題7(1)用自然語(yǔ)言描述以下文法定義語(yǔ)言G:AaaA|aaBBBcc|D#ccDbbbD|#解題思緒觀察每個(gè)產(chǎn)生式及其組合產(chǎn)生子語(yǔ)言特點(diǎn)；依據(jù)開(kāi)始符產(chǎn)生式將它們并起來(lái)就是整個(gè)文法產(chǎn)生語(yǔ)言；解答(1)D產(chǎn)生式：DbbbD|#使用DbbbD可產(chǎn)生句型：(bbb)mD(m1);深入使用D#可得：L(D)={(bbb)m#|m0}GHF/10/109(C)GuohongFu,CS@HLJU第9頁(yè)課后作業(yè)二(cont.)(2)B產(chǎn)生式：BBcc|D#cc用產(chǎn)生式BBcc產(chǎn)生句型：B(cc)n(n1);結(jié)合BD#cc產(chǎn)生句型：D#cc;利用(1)中結(jié)果，L(B)={(bbb)m##(cc)n|m0，n1}(3)A產(chǎn)生式：AaaA|aaB用產(chǎn)生式AaaA產(chǎn)生句型：(aa)kA(k1);結(jié)合產(chǎn)生式AaaB產(chǎn)生句型：(aa)kB(k1);利用(1)中結(jié)果，L(A)={(aa)k(bbb)m##(cc)n|k1,m0,n1}GHF/10/1010(C)GuohongFu,CS@HLJU第10頁(yè)課后作業(yè)二(cont.)pp.84：習(xí)題8設(shè)={0,1}，結(jié)構(gòu)產(chǎn)生以下語(yǔ)言文法(1)全部以0開(kāi)頭串；(3)全部以11開(kāi)頭，以11結(jié)尾串；8(1)解答分析語(yǔ)言特點(diǎn):{0x|x{0,1}*}；產(chǎn)生子語(yǔ)言{x|x{0,1}*}文法A|0A|1A；產(chǎn)生語(yǔ)言{0x|x{0,1}*}文法S0A；G:S0AA|0A|1AGHF/10/1011(C)GuohongFu,CS@HLJU第11頁(yè)課后作業(yè)二(cont.)習(xí)題8(3)解答分析：語(yǔ)言特點(diǎn){11x11|x*}{111,11}；產(chǎn)生語(yǔ)言{x|x{0,1}*}文法A|0A|1A；產(chǎn)生子語(yǔ)言{11x11|x*}文法S11A11；產(chǎn)生子語(yǔ)言{111,11}文法S111|11；G:S11A11|111|11A|0A|1AGHF其它答案(1)G:S11A|111|11A11|0A|1A(2)G:S11A|111|11AB11B|0B|1B/10/1012(C)GuohongFu,CS@HLJU第12頁(yè)課后作業(yè)二(cont.)pp.84：習(xí)題9(2)設(shè)={a,b,c}，結(jié)構(gòu)產(chǎn)生以下語(yǔ)言文法(2)L2={anbm|m,n1}；解答分析語(yǔ)言特點(diǎn)：表示最少一個(gè)a和最少一個(gè)b組成，且全部a位于b之前a、b串集合。產(chǎn)生子語(yǔ)言La={an|n1}文法：Ga:Aa|aA產(chǎn)生子語(yǔ)言Lb={bm|m1}文法：Gb:Bb|bB利用L2={anbm|m,n1}同子語(yǔ)言La、Lb關(guān)系，即L2=LaLb，可得文法

G2:SAB---a子串和b子串位置關(guān)系 Aa|aABb|bB;GHF/10/1013(C)GuohongFu,CS@HLJU第13頁(yè)課后作業(yè)三pp.126-130---DFA習(xí)題1---DFA基本概念習(xí)題2(3)---RLDFA習(xí)題2(5)---RLDFA習(xí)題7---擴(kuò)展?fàn)顟B(tài)轉(zhuǎn)移函數(shù)GHF/10/1014(C)GuohongFu,CS@HLJU第14頁(yè)課后作業(yè)三(cont.)pp.126習(xí)題1(1)圖1：q0q3q1q3q2q3q1q3；圖2：q0q2q3q1q3q2q3q1(2)DFA識(shí)別串過(guò)程形式描述可用即時(shí)描述表示pp.126習(xí)題2(1)Sq00,1L1={0,1}*GHF/10/1015(C)GuohongFu,CS@HLJU第15頁(yè)課后作業(yè)三(cont.)習(xí)題2(3)

結(jié)構(gòu)DFAM，使得L(M)={x|x{0,1}+,且x不含00子串}解答：采取畫(huà)圖法依據(jù)語(yǔ)言特點(diǎn)定義狀態(tài)

q0-開(kāi)始狀態(tài)；

q1-M讀到一個(gè)0，并等候讀一個(gè)1；q2-M讀到一個(gè)1，并等候讀更多1；依據(jù)狀態(tài)定義設(shè)計(jì)主體框架依據(jù)輸入字母表補(bǔ)充細(xì)節(jié)qtq21Sq01q100,1001GHF/10/1016(C)GuohongFu,CS@HLJU第16頁(yè)課后作業(yè)三(cont.)習(xí)題2(5)：結(jié)構(gòu)DFAM，使得L(M)={x|x{0,1}+,且x含形如10110子串}解答：畫(huà)圖法(1)依據(jù)語(yǔ)言特點(diǎn)定義狀態(tài)

q0-開(kāi)始狀態(tài)，等候讀一個(gè)1；

q1-M讀到10110第一個(gè)1，并等候讀一個(gè)0或更多1；q2-M在讀到第一個(gè)1后繼續(xù)讀到一個(gè)0，并等候讀一個(gè)1；q3-M在相繼讀到1和0后讀到一個(gè)1，并等候讀下一個(gè)1；q4-M在相繼讀到1,

0和1后讀到一個(gè)1，并等候讀一個(gè)0；q5-終止?fàn)顟B(tài)：M在相繼讀到1,

0,1和1后讀到一個(gè)0，并等候讀更多0或1；GHF/10/1017(C)GuohongFu,CS@HLJU第17頁(yè)課后作業(yè)三(cont.)(2)依據(jù)狀態(tài)定義包括主體框架(3)依據(jù)輸入字母表補(bǔ)充細(xì)節(jié)q1q51Sq010q20q31q4100,1001GHF/10/1018(C)GuohongFu,CS@HLJU第18頁(yè)課后作業(yè)三(cont.)pp.127習(xí)題7：設(shè)DFAM=(Q,,,q0,F)，證實(shí)：x,y*,(q,xy)=((q,x),y)證實(shí)：施歸納于|y|基礎(chǔ)：當(dāng)|y|=0時(shí)，y=(q,xy)=(q,x)=(q,x)

//x*,x=x((q,x),y)=((q,x),)=(q,x)

//pQ,(p,)=p

即(q,xy)=((q,x),y)，結(jié)論成立歸納：設(shè)當(dāng)|y|k(k0)時(shí)結(jié)論成立，往證|y|=k+1結(jié)論成立不妨設(shè)y=ya,a，顯然|ya|=k+1(q,xy)=(q,xya)

=((q,xy),a)

//擴(kuò)展?fàn)顟B(tài)轉(zhuǎn)移函數(shù)定義(q,xa)=((q,x),a)

=(((q,x),y),a)

//歸納假設(shè)：(q,xy)=((q,x),y)

=((q,x),ya)

//擴(kuò)展?fàn)顟B(tài)轉(zhuǎn)移函數(shù)定義(q,xa)=((q,x),a)

即(q,xya)=((q,x),ya)，結(jié)論成立由歸納原理：x,y*,(q,xy)=((q,x),y)成立。

GHF/10/1019(C)GuohongFu,CS@HLJU第19頁(yè)課后作業(yè)四pp.128-129習(xí)題11(1)---NFADFA習(xí)題15(1)----NFANFAGHF/10/1020(C)GuohongFu,CS@HLJU第20頁(yè)課后作業(yè)四(cont.)pp.128習(xí)題11(1)

結(jié)構(gòu)與NFAM等價(jià)DFAM012→q0{q0,q1}{q0,q2}{q0,q2}q1{q0,q3}Φ{q2}q2Φ{q1,q3}{q1,q2}*q3{q2,q3}{q3}{q0}狀態(tài)012[q0][q0,q1][q0,q2][q0,q2][q1][q0,q3][][q2][q2][][q1,q3][q1,q2]*[q3][q2,q3][q3][q0][q0,q1][q0,q1,q3][q0,q2][q0,q2][q0,q2][q0,q1][q0,q2,q3][q0,q1,q2]*[q0,q3][q0,q1,q2,

q3][q0,q2,q3][q0,q2][q1,q2][q3,q3][q1,q3][q1,q2]*[q1,q3][q0,q2,q3][q3][q0,q2]*[q2,q3][q2,q3][q1,q3][q0,q1,q2][q0,q1,q2][q0,q1,q3][q0,q1,q2,

q3][q0,q1,q2]*[q0,q1,q3][q0,q1,q2,

q3][q0,q2,q3][q0,q2]*[q0,q2,q3][q0,q1,q2,

q3][q0,q1,q2,

q3][q0,q1,q2]*[q1,q2,q3][q0,q2,

q3][q1,q3][q0,q1,q2]*[q0,q1,q2,q3][q0,q1,q2,

q3][q0,q1,q2,

q3][q0,q1,q2]

[][][][](1)針對(duì)M全部狀態(tài)子

集S和全部輸入符號(hào)計(jì)算

D(S,a)M狀態(tài)轉(zhuǎn)移表M狀態(tài)子集轉(zhuǎn)移表

解答：子集結(jié)構(gòu)法GHF/10/1021(C)GuohongFu,CS@HLJU第21頁(yè)課后作業(yè)四(cont.)(2)確定可達(dá)狀態(tài)012→q0{q0,q1}{q0,q2}{q0,q2}q1{q0,q3}Φ{q2}q2Φ{q1,q3}{q1,q2}*q3{q2,q3}{q3}{q0}狀態(tài)012[q0][q0,q1][q0,q2][q0,q2][q1][q0,q3][][q2][q2][][q1,q3][q1,q2]*[q3][q2,q3][q3][q0][q0,q1][q0,q1,q3][q0,q2][q0,q2][q0,q2][q0,q1][q0,q2,q3][q0,q1,q2]*[q0,q3][q0,q1,q2,

q3][q0,q2,q3][q0,q2][q1,q2][q0,q3][q1,q3][q1,q2]*[q1,q3][q0,q2,q3][q3][q0,q2]*[q2,q3][q2,q3][q1,q3][q0,q1,q2][q0,q1,q2][q0,q1,q3][q0,q1,q2,

q3][q0,q1,q2]*[q0,q1,q3][q0,q1,q2,

q3][q0,q2,q3][q0,q2]*[q0,q2,q3][q0,q1,q2,

q3][q0,q1,q2,

q3][q0,q1,q2]*[q1,q2,q3][q0,q2,

q3][q1,q3][q0,q1,q2]*[q0,q1,q2,q3][q0,q1,q2,

q3][q0,q1,q2,

q3][q0,q1,q2]

[][][][]M狀態(tài)轉(zhuǎn)移表M狀態(tài)轉(zhuǎn)移表GHF/10/1022(C)GuohongFu,CS@HLJU第22頁(yè)課后作業(yè)四(cont.)(3)去除不可達(dá)狀態(tài)狀態(tài)012[q0][q0,q1][q0,q2][q0,q2][q0,q1][q0,q1,q3][q0,q2][q0,q2][q0,q2][q0,q1][q0,q2,q3][q0,q1,q2][q0,q1,q2][q0,q1,q3][q0,q1,q2,

q3][q0,q1,q2]*[q0,q1,q3][q0,q1,q2,

q3][q0,q2,q3][q0,q2]*[q0,q2,q3][q0,q1,q2,

q3][q0,q1,q2,

q3][q0,q1,q2]*[q0,q1,q2,q3][q0,q1,q2,

q3][q0,q1,q2,

q3][q0,q1,q2]與M等價(jià)DFAM狀態(tài)轉(zhuǎn)移表[q0,q2][q0,q2,q3]001,21S[q0]2[q0,q1][q0,q1,q3]01,201[q0,q1,q2][q0,q1,q2,q3]2210,10,120GHF/10/1023(C)GuohongFu,CS@HLJU第23頁(yè)課后作業(yè)四(cont.)pp.129：習(xí)題15(1)：依據(jù)下表給定-NFAM結(jié)構(gòu)與之等價(jià)NFAMN確定FN因?yàn)?CLOSURE(q0)={q0,q1,q2}F=則FN

=F={q3}經(jīng)過(guò)計(jì)算(q,a)，確定N(q,a)=(q,a)即可得到NFAMN=(Q,,N,q0,FN)01→q0{q0,q1}{q0,q2}{q0,q2}q1{q0,q3}Φ{q2}q2Φ{q1,q3}{q1,q2}*q3{q2,q3}{q3}{q0}(q,a)=-CLOSURE(((q,),a)狀態(tài)01q0{q0,q1,q2}{q0,q1,q2,q3}{q0,q1,q2,q3}q1{q1,q2}{q0,q1,q2,q3}{q0,q1,q2,q3}q2{q1,q2}{q0,q1,q2,q3}{q0,q1,q2,q3}*q3{q0,q1,q2,q3}{q0,q1,q2,q3}{q0,q1,q2,q3}(q0,0)=-CLOSURE(((q0,),0)=-CLOSURE(({q0,q1,q2},0)=-CLOSURE((q0,0)(q1,0)(q2,0))=-CLOSURE({q0,q1}{q0,q3}Φ)=-CLOSURE({q0,q1,q3})=-CLOSURE(q0)-CLOSURE(q1)-CLOSURE(q3)={q0,q1,q2}{q1,q2}{q0,q1,q2,q3}={q0,q1,q2,q3}0,10,1S0,1q1q3q0q20,10,10,10,10,10,10,1(q0,1)=-CLOSURE(((q0,),1)=-CLOSURE(({q0,q1,q2},1)=-CLOSURE((q0,1)(q1,1)(q2,1))=-CLOSURE({q0,q2}{q1,q3})=-CLOSURE({q0,q1,q2,q3})=-CLOSURE(q0)-CLOSURE(q1)-CLOSURE(q2)-CLOSURE(q3)={q0,q1,q2}{q1,q2}{q1,q2}{q0,q1,q2,q3}={q0,q1,q2,q3}(q1,0)=-CLOSURE(((q1,),0)=-CLOSURE(({q1,q2},0)=-CLOSURE((q1,0)(q2,0))=-CLOSURE({q0,q3})=-CLOSURE({q0,q3})=-CLOSURE(q0)-CLOSURE(q3)={q0,q1,q2}{q0,q1,q2,q3}={q0,q1,q2,q3}(q1,1)=-CLOSURE(((q1,),1)=-CLOSURE(({q1,q2},1)=-CLOSURE((q1,1)(q2,1))=-CLOSURE({q1,q3})=-CLOSURE({q1,q3})=-CLOSURE(q1)-CLOSURE(q3)={q1,q2}{q0,q1,q2,q3}={q0,q1,q2,q3}(q2,0)=-CLOSURE(((q2,),0)=-CLOSURE(({q1,q2},0)=-CLOSURE((q1,0)(q2,0))=-CLOSURE({q0,q3})=-CLOSURE({q0,q3})=-CLOSURE(q0)-CLOSURE(q3)={q0,q1,q2}{q0,q1,q2,q3}={q0,q1,q2,q3}(q2,1)=-CLOSURE(((q2,),1)=-CLOSURE(({q1,q2},1)=-CLOSURE((q1,1)(q2,1))=-CLOSURE({q1,q3})=-CLOSURE({q1,q3})=-CLOSURE(q1)-CLOSURE(q3)={q1,q2}{q0,q1,q2,q3}={q0,q1,q2,q3}(q3,0)=-CLOSURE(((q3,),0)=-CLOSURE(({q0,q1,q2,q3},0)=-CLOSURE((q0,0)

(q1,0)(q2,0)(q3,0))=-CLOSURE({q0,q1}{q0,q3}{q2,q3})=-CLOSURE({q0,q1,q2,q3})=-CLOSURE(q0)

-CLOSURE(q1)

-CLOSURE(q2)

-CLOSURE(q3)={q0,q1,q2}{q1,q2}{q1,q2}

{q0,q1,q2,q3}={q0,q1,q2,q3}(q3,1)=-CLOSURE(((q3,),1)=-CLOSURE(({q0,q1,q2,q3},1)=-CLOSURE((q0,1)

(q1,1)(q2,1)(q3,1))=-CLOSURE({q0,q2}{q1,q3}{q3})=-CLOSURE({q0,q1,q2,q3})=-CLOSURE(q0)

-CLOSURE(q1)

-CLOSURE(q2)

-CLOSURE(q3)={q0,q1,q2}{q1,q2}{q1,q2}

{q0,q1,q2,q3}={q0,q1,q2,q3}GHF/10/1024(C)GuohongFu,CS@HLJU第24頁(yè)課后作業(yè)四(cont.)pp.128：習(xí)題15(2)：依據(jù)下表給定-NFAM4結(jié)構(gòu)與之等價(jià)NFAMN4確定FN4因?yàn)?CLOSURE(q0)={q0,q1,q3}F3則FN4

=F4{q0}={q0,q3}經(jīng)過(guò)計(jì)算4(q,a)，確定N4=4(q,a)即可得到NFAMN4=(Q,,N4,q0,FN4)=-CLOSURE(((q,),a)狀態(tài)01*q0{q0,q1,q3}{q1,q2,q3}{q0,q1,q2,q3}q1{q1}{q2,q3}{q1,q2,q3}q2{q2,q3}{q2,q3}{q0,q1,q3}*q3{q3}Φ{q0,q1,q3}01→q0{q1,q3}{q1}{q1,q3}q1{q2}{q1,q2}Φq2{q2,q3}{q0}{q2,q3}*q3Φ{q0}Φ(q0,0)=-CLOSURE(((q0,),0)=-CLOSURE(({q0,q1,q3},0)=-CLOSURE((q0,0)(q1,0)(q3,0))=-CLOSURE({q1,q3}{q2})=-CLOSURE({q1,q2,q3})=-CLOSURE(q1)-CLOSURE(q2)-CLOSURE(q3)={q1}{q2,q3}{q3}={q1,q2,q3}(q0,1)=-CLOSURE(((q0,),1)=-CLOSURE(({q0,q1,q3},1)=-CLOSURE((q0,1)(q1,1)(q3,1))=-CLOSURE({q1}{q1,q2}{q0})=-CLOSURE({q0,q1,q2})=-CLOSURE(q0)-CLOSURE(q1)-CLOSURE(q2)={q0,q1,q3}{q1}{q2,q3}={q0,q1,q2,q3}(q1,0)=-CLOSURE(((q1,),0)=-CLOSURE(({q1},0)=-CLOSURE((q1,0))=-CLOSURE({q2})=-CLOSURE(q2)={q2,q3}(q1,1)=-CLOSURE(((q1,),1)=-CLOSURE(({q1},1)=-CLOSURE((q1,1))=-CLOSURE({q1,q2})=-CLOSURE(q1)-CLOSURE(q2)={q1}{q2,q3}={q1,q2,q3}(q2,0)=-CLOSURE(((q2,),0)=-CLOSURE(({q2,q3},0)=-CLOSURE((q2,0)(q3,0))=-CLOSURE({q2,q3}Φ)=-CLOSURE({q2,q3})=-CLOSURE(q2)-CLOSURE(q3)={q2,q3}{q3}={q2,q3}(q2,1)=-CLOSURE(((q2,),1)=-CLOSURE(({q2,q3},1)=-CLOSURE((q2,1)(q3,1))=-CLOSURE({q0}{q0}=-CLOSURE({q0})=-CLOSURE(q0)={q0,q1,q3}(q3,0)=-CLOSURE(((q3,),0)=-CLOSURE(({q3},0)=-CLOSURE((q3,1))=-CLOSURE(Φ)=Φ(q3,1)=-CLOSURE(((q3,),1)=-CLOSURE(({q3},1)=-CLOSURE((q3,1))=-CLOSURE(q0)={q0,q1,q3}S0,11q1q3q2110,1010,1q0GHF/10/1025(C)GuohongFu,CS@HLJU第25頁(yè)課后作業(yè)五pp.129-130

：FARG習(xí)題20---DFA右線性文法習(xí)題21---DFA左線性文法習(xí)題22(1)---右線性文法FA(2)---左線性文法FAGHF/10/1026(C)GuohongFu,CS@HLJU第26頁(yè)課后作業(yè)五(cont.)習(xí)題20(a)

結(jié)構(gòu)DFAM1等價(jià)右線性文法G1(3)對(duì)M1每個(gè)狀態(tài)轉(zhuǎn)移(q,a)=p，確定對(duì)應(yīng)產(chǎn)生式qap：(q0,0)=q1q00q1(q0,1)=q3q01q3(q1,0)=q0q10q0(q1,1)=q3q11q3(q3,0)=q1q30q1(q3,1)=q1q31q1(1)刪除不可達(dá)狀態(tài)q2

(3)對(duì)M狀態(tài)轉(zhuǎn)移(q,a)=pF，確定對(duì)應(yīng)產(chǎn)生式qa：(q0,1)=q3q01(q1,1)=q3q11G1:q01|0q1|1q3q11|0q0|1q3q30q1|1q1q1Sq20,1q301100q01(2)確定V,T和SV={q0,q1,q3}T={0,1}S=q0GHF/10/1027(C)GuohongFu,CS@HLJU第27頁(yè)課后作業(yè)五(cont.)習(xí)題20(b)結(jié)構(gòu)DFAM2等價(jià)右線性文法G2(2)對(duì)M2每個(gè)狀態(tài)轉(zhuǎn)移(q,a)=p，確定對(duì)應(yīng)產(chǎn)生式qap：(q0,0)=q1q00q1(q0,1)=q2q01q2(q1,0)=q2q10q2(q1,1)=q0q11q0(q2,0)=q3q20q3(q2,1)=q1q21q1(q3,0)=q1q30q1(q3,1)=q1q31q1(3)對(duì)M狀態(tài)轉(zhuǎn)移(q,a)=pF，確定對(duì)應(yīng)產(chǎn)生式qa：(q1,1)=q0q11(q2,0)=q3q20G2:q0|0q1|1q2q11|0q2|1q0q20|0q3|1q1q30q1|1q1(1)確定V,T和SV={q0,q1,q2,q3}T={0,1}S=q0q1Sq20,1q30q010011(4)假如M開(kāi)始狀

態(tài)q0又是接收狀態(tài),

則需引入空產(chǎn)生式

q0以產(chǎn)生空語(yǔ)句GHF/10/1028(C)GuohongFu,CS@HLJU第28頁(yè)課后作業(yè)五(cont.)習(xí)題21(a)結(jié)構(gòu)DFAM1等價(jià)左線性文法G1q1Sq20,1q301100q01(3)對(duì)M1每個(gè)狀態(tài)轉(zhuǎn)移(A,a)=B，確定對(duì)應(yīng)產(chǎn)生式BAa：

(q0,0)=q1q1q00(q0,1)=q3q3q01(q1,0)=q0q0q10(q1,1)=q3q3q11(q3,0)=q1q1q30(q3,1)=q1q1q31(1)刪除M1不可達(dá)狀態(tài)及相關(guān)??；(4)對(duì)M1狀態(tài)轉(zhuǎn)移(A,a)=B，且A為開(kāi)始狀態(tài)，確定對(duì)應(yīng)產(chǎn)生式Ba：

(q0,0)=q1q10(q0,1)=q3q31G1:Zq01|q11q0q10q10|q00|q30|q31q31|q01|q11(5)對(duì)M1狀態(tài)轉(zhuǎn)移(A,a)=BF，確定對(duì)應(yīng)產(chǎn)生式ZAa(q0,1)=q3Zq01(q1,1)=q3Zq11GHF(2)確定V,T和SV={q0,q1,q3,Z}T={0,1}S=Z/10/1029(C)GuohongFu,CS@HLJU第29頁(yè)課后作業(yè)五(cont.)習(xí)題21(b)結(jié)構(gòu)DFAM2等價(jià)左線性文法G2(2)對(duì)M2每個(gè)狀態(tài)轉(zhuǎn)移(A,a)=B，確定對(duì)應(yīng)產(chǎn)生式BAa：

(q0,0)=q1q1q00(q0,1)=q2q2q01(q1,0)=q2q2q10(q1,1)=q0q0q11(q2,0)=q3q3q20(q2,1)=q1q1q21(q3,0)=q1q1q30(q3,1)=q1q1q31(3)對(duì)M2狀態(tài)轉(zhuǎn)移(A,a)=B，且A為開(kāi)始狀態(tài)，確定對(duì)應(yīng)產(chǎn)生式Ba：

(q0,0)=q1q10(q0,1)=q2q21G2:Z|q11|q20q0q11q10|q00|q20|q21q30|q31q21|q01|q10q3q20(4)對(duì)M2狀態(tài)轉(zhuǎn)移(A,a)=BF，確定對(duì)應(yīng)產(chǎn)生式ZAa(q1,1)=q0Zq11(q2,0)=q3Zq20q1Sq20,1q30q010011(5)因M2開(kāi)始狀態(tài)又是終止?fàn)顟B(tài)，須引入空產(chǎn)生式確定Z來(lái)歸約空句子GHF(1)確定V,T和SV={q0,q1,q2,

q3,Z}T={0,1}S=Z/10/1030(C)GuohongFu,CS@HLJU第30頁(yè)課后作業(yè)五(cont.)pp.129習(xí)題22(1):結(jié)構(gòu)與所給文法等價(jià)FA

(2)對(duì)G中形如AaB產(chǎn)生式確定對(duì)應(yīng)狀態(tài)轉(zhuǎn)移函數(shù)(A,a)={B}：SaA(S,a)={A}AaA(A,a)={A}AcA(A,c)={A}AbB(A,b)={B}BaB(B,a)={B}BbB

(B,b)={B}BcB

(B,c)={B}(1)確定Q,,q0和FQ=V∪{Z}={S,A,B,Z}

={a,b,c}q0=S

F={Z}(3)對(duì)G中形如Aa產(chǎn)生式確定對(duì)應(yīng)狀態(tài)轉(zhuǎn)移函數(shù)(A,a)={Z}：Sa(S,a)={Z}Aa(A,a)={Z}Ba(B,a)={Z}Bb(B,b)={Z}Bc(B,c)={Z}G1:Sa|aAAa|aA|cA|bBBa|b|c|aB|bB|cBSABZSaaa,b,caba,ca,b,cGHF/10/1031(C)GuohongFu,CS@HLJU第31頁(yè)課后作業(yè)五(cont.)pp.129習(xí)題22(2):結(jié)構(gòu)與所給文法等價(jià)FA

(2)對(duì)G中形如ABa產(chǎn)生式確定對(duì)應(yīng)狀態(tài)轉(zhuǎn)移函數(shù)(B,a)={A}：SAa(A,a)={S}AAa(A,a)={A}AAc(A,c)={A}ABb(B,b)={A}BBa(B,a)={B}BBb

(B,b)={B}BBc

(B,c)={B}(1)確定Q,,q0和FQ=V∪{Z}={S,A,B,Z}

={a,b,c}q0=Z

F={S}(3)對(duì)G中形如Aa產(chǎn)生式確定對(duì)應(yīng)狀態(tài)轉(zhuǎn)移函數(shù)(Z,a)={A}：Sa(Z,a)={S}Aa(Z,a)={A}Ba(Z,a)={B}Bb(Z,b)={B}Bc(Z,c)={B}G2:Sa|AaAa|Aa|Ac|BbBa|b|c|Ba|Bb|BcZABSSaaaba,ca,b,ca,b,cGHF/10/1032(C)GuohongFu,CS@HLJU第32頁(yè)課后作業(yè)六pp.153-155習(xí)題1(5)---RLRE習(xí)題2(2)---RERL習(xí)題5(2)---REFA習(xí)題6(圖4-24)---FAREGHF/10/1033(C)GuohongFu,CS@HLJU第33頁(yè)課后作業(yè)六(cont.)習(xí)題1(5)

寫(xiě)出表示以下語(yǔ)言正則表示式：

(5){x|x{0,1}+且x含形如10110子串}解答語(yǔ)言{x|x{0,1}+且x含形如10110子串}可等價(jià)表示為

{0,1}*10110{0,1}*{0,1}*RE為(0+1)*所以(0+1)*10110(0+1)*即為所求。GHF/10/1034(C)GuohongFu,CS@HLJU第34頁(yè)課后作業(yè)六(cont.)習(xí)題2(2)

了解以下正則表示式，說(shuō)明它們表示語(yǔ)言：(2)(0+1)*0100+解答L((0+1)*0100+)={x|x為以010子串后跟最少一個(gè)0組成串為后綴任意0和1組成字符串}GHF/10/1035(C)GuohongFu,CS@HLJU第35頁(yè)課后作業(yè)六(cont.)習(xí)題5(2)

結(jié)構(gòu)以下正則表示式等價(jià)FA：(2)00(0+1)*((01)*+010)00解答(1)結(jié)構(gòu)與00等價(jià)ε-NFAM1;00S(2)結(jié)構(gòu)與00(0+1)*等價(jià)ε-NFAM2;01(3)結(jié)構(gòu)與(01)*等價(jià)ε-NFAM3;(4)結(jié)構(gòu)與010等價(jià)ε-NFAM4;(5)結(jié)構(gòu)與(01)*+010等價(jià)ε-NFAM5;(6)結(jié)構(gòu)與((01)*+010)00等價(jià)ε-NFAM6;00(7)結(jié)構(gòu)與00(0+1)*((01)*+010)00等價(jià)ε-NFAM7;10010GHF/10/1036(C)GuohongFu,CS@HLJU第36頁(yè)課后作業(yè)六(cont.)習(xí)題6(圖4-24)

結(jié)構(gòu)下列圖所表示DFA正則表示式q1Sq20q30q0110011GHF/10/1037(C)GuohongFu,CS@HLJU第37頁(yè)課后作業(yè)六(cont.)解答(1)預(yù)處理q1Sq20q30q011001q0q3XY1GHF/10/1038(C)GuohongFu,CS@HLJU第38頁(yè)課后作業(yè)六(cont.)(2)去狀態(tài)q3q1q20011001q0q3XY1010001011110111GHF/10/1039(C)GuohongFu,CS@HLJU第39頁(yè)課后作業(yè)六(cont.)(3)合并從標(biāo)識(shí)為q0狀態(tài)到標(biāo)識(shí)為q1狀態(tài)兩條并行弧q1q2010q0XY010001011110111+10GHF/10/1040(C)GuohongFu,CS@HLJU第40頁(yè)課后作業(yè)六(cont.)(4)去掉狀態(tài)q2q1q210q0XY01000101111110+1011(01)*111(01)*0011(01)*011(01)*0011(01)*011(01)*1GHF/10/1041(C)GuohongFu,CS@HLJU第41頁(yè)課后作業(yè)六(cont.)(5)合并從標(biāo)識(shí)為q0狀態(tài)到標(biāo)識(shí)為q1狀態(tài)兩條并行弧q10q0XY10110+1011(01)*111(01)*0011(01)*011(01)*0011(01)*011(01)*1+11(01)*00GHF/10/1042(C)GuohongFu,CS@HLJU第42頁(yè)課后作業(yè)六(cont.)(6)合并從標(biāo)識(shí)為q1狀態(tài)到標(biāo)識(shí)為q0狀態(tài)兩條并行弧q10q0XY10110+1011(01)*111(01)*011(01)*0011(01)*011(01)*1+11(01)*00+0GHF/10/1043(C)GuohongFu,CS@HLJU第43頁(yè)課后作業(yè)六(cont.)(7)合并從標(biāo)識(shí)為q0狀態(tài)到標(biāo)識(shí)為Y狀態(tài)兩條并行弧q1q0XY10110+1011(01)*111(01)*011(01)*0011(01)*011(01)*1+11(01)*00+0+1+GHF/10/1044(C)GuohongFu,CS@HLJU第44頁(yè)課后作業(yè)六(cont.)(8)合并從標(biāo)識(shí)為q0狀態(tài)到標(biāo)識(shí)為Y狀態(tài)兩條并行弧q1q0XY1010+1011(01)*111(01)*011(01)*0011(01)*011(01)*1+11(01)*00+0+1+GHF/10/1045(C)GuohongFu,CS@HLJU第45頁(yè)課后作業(yè)六(cont.)(9)合并從標(biāo)識(shí)為q1狀態(tài)到標(biāo)識(shí)為Y狀態(tài)兩條并行弧q1q0XY1010+1011(01)*111(01)*011(01)*0011(01)*011(01)*1+11(01)*00+0+1++11(01)*0GHF/10/1046(C)GuohongFu,CS@HLJU第46頁(yè)課后作業(yè)六(cont.)(10)合并從標(biāo)識(shí)為q1狀態(tài)到標(biāo)識(shí)為q1狀態(tài)兩條并行弧q1q0XY100+1011(01)*111(01)*011(01)*0011(01)*1+11(01)*00+0+1+1+11(01)*0+11(01)*00GHF/10/1047(C)GuohongFu,CS@HLJU第47頁(yè)課后作業(yè)六(cont.)(11)去掉狀態(tài)q1q1q0XY11(01)*111(01)*011(01)*1+00+10+11(01)*00+1+1+11(01)*010+11(01)*00(0+10+11(01)*00)(10+11(01)*00)*(1+11(01)*0)(0+10+11(01)*00)(10+11(01)*00)*(0+11(01)*1)GHF/10/1048(C)GuohongFu,CS@HLJU第48頁(yè)課后作業(yè)六(cont.)(12)合并從標(biāo)識(shí)為q0狀態(tài)到標(biāo)識(shí)為q0狀態(tài)兩條并行弧q0XY11(01)*111(01)*0+1+(0+10+11(01)*00)(10+11(01)*00)*(1+11(01)*0)(0+10+11(01)*00)(10+11(01)*00)*(0+11(01)*1)+11(01)*1GHF/10/1049(C)GuohongFu,CS@HLJU第49頁(yè)課后作業(yè)六(cont.)(13)合并從標(biāo)識(shí)為q0狀態(tài)到標(biāo)識(shí)為Y狀態(tài)兩條并行弧q0XY11(01)*0+1+(0+10+11(01)*00)(10+11(01)*00)*(1+11(01)*0)(0+10+11(01)*00)(10+11(01)*00)*(0+11(01)*1)+11(01)*1+11(01)*0+1+GHF/10/1050(C)GuohongFu,CS@HLJU第50頁(yè)課后作業(yè)六(cont.)(14)去掉q0q0XY(0+10+11(01)*00)(10+11(01)*00)*(1+11(01)*0)(0+10+11(01)*00)(10+11(01)*00)*(0+11(01)*1)+11(01)*1+11(01)*0+1+((0+10+11(01)*00)(10+11(01)*00)*(0+11(01)*1)+11(01)*1)*((0+10+11(01)*00)(10+11(01)*00)*(1+11(01)*0)+11(01)*0+1+)GHF/10/1051(C)GuohongFu,CS@HLJU第51頁(yè)課后作業(yè)七pp.191習(xí)題2---RL泵引理應(yīng)用

判斷以下語(yǔ)言是否是RL。假如不是，證實(shí)你結(jié)論；假如是，給出對(duì)應(yīng)有窮描述。

(1){02n|n1}(2){0n2|n1}GHF/10/1052(C)GuohongFu,CS@HLJU第52頁(yè)課后作業(yè)七(cont.)pp.191習(xí)題2(1)：{02n|n1}解答：是RL語(yǔ)言：表示偶數(shù)個(gè)0組成字串集合模型：RE:(00)+或00(00)*；RG:S00|00S；-NFA

q0Sq1q3q4q20000GHF/10/1053(C)GuohongFu,CS@HLJU第53頁(yè)課后作業(yè)七(cont.)pp.191習(xí)題2(2)：{0n2|n1}解答：不是RL用泵引理證實(shí)(1)假設(shè)L={0n2|n1}是RL(2)取z=0N2,zL(3)按照泵引理，一定存在z=uvw，取v=0k(1kN)，此時(shí)u=0N-k-jw=0N2+j-N

(4)從而有，uviw=0N-k-j(0k)i0N2+j-N=0N2+(i-1)k

GHF/10/1054(C)GuohongFu,CS@HLJU第54頁(yè)課后作業(yè)七(cont.)(5)當(dāng)i=2時(shí)，有：N2+(i-1)k=N2+kN2+N=N(N+1)<(N+1)2；同時(shí)N2+(i-1)k=N2+k>N2；表明：N2+(i-1)k不是整數(shù)平方；(6)即：i=2時(shí)uviwL；這與泵引理矛盾；所以，L不是RL。GHF/10/1055(C)GuohongFu,CS@HLJU第55頁(yè)課后作業(yè)八pp.230---CFG化簡(jiǎn)習(xí)題11(1)---去無(wú)用符習(xí)題12(2)---去空產(chǎn)生式GHF/10/1056(C)GuohongFu,CS@HLJU第56頁(yè)課后作業(yè)八(cont.)pp.230

習(xí)題11(1)刪除以下文法中無(wú)用符號(hào)解答方法：先用算法6-1消除不可產(chǎn)生變量，后用算法6-2消除不可達(dá)符號(hào)(1)用算法6-1刪除派生不可產(chǎn)生變量D和E得到(2)用算法6-2可知，上述文法不存在不可大符號(hào)SAB|CA|aAaBBC|AB|DE|