第二章——習(xí)題答案1.設(shè)T1＝{11，010}，T2＝{0，01，1001}，計算：T2T1，T1*，T2+。T2T1＝{011，0010，0111，01010，100111，1001010}T1*＝{ε，11，010，1111，11010，01011，010010……}T2+＝{0，01，1001，00，001，01001，010，0101……}2.令A(yù)＝{0，1，2}，寫出集合A+和A*的七個最短符號串。A+：0，1，2，00，01，02，10（有多種可能）A*：ε，0，1，2，00，01，02（有多種可能）3.試證明：A+＝AA*＝A*A。證明：A+＝A1∪A2∪……∪An∪……A*＝A0（即{ε}）∪A+AA*＝A（A0∪A+）＝A∪A2∪A3∪A4……＝A+＝A+∪A＝（A0∪A+）A＝A*A（證畢）4.設(shè)有文法G[S]：S∷＝AA∷＝B|iAtAeAB∷＝C|B+C|+CC∷＝D|C*D|*DD∷＝x|(A)|-D試寫出VN和VT。VN＝{S，A，B，C，D}VT＝{i，t，e，+，*，x，(，)，-}5.設(shè)有文法G[S]：S∷＝aAbA∷＝BcA|BB∷＝idt|ε試問下列符號串（1）aidtcBcAb（2）ab（3）adibt（4）aidtcidtcidtb是否為該文法的句型或句子。（1）SaAbaBcAbaidtcAbaidtcBcAb是句型但不是句子；（2）SaAbaBbaεbab是句型也是句子；（3）沒有一條規(guī)則可以用b置換idt中的d，所以adibt既不是句型也不是句子；（4）SaAbaBcAbaidtcAbaidtcBcAbaidtcidtcBbaidtcidtcidtb是句型也是句子。6.給定文法：S∷＝aB|bAA∷＝aS|bAA|aB∷＝bS|aBB|b該文法所描述的語言是什么？L(G)＝{相同個數(shù)的a與b以任意次序連接而成的非空符號串}。7.試分別描述下列文法所產(chǎn)生的語言（文法開始符號為S）：S∷＝0S|01S∷＝aaS|bcS∷=aSd|aAdA∷=aAc|bcS∷=ABA∷=aAb|abB∷=cBd|εL(G)＝{0n1|n≥1}；{解題思路：將文法轉(zhuǎn)換為正規(guī)表達式}L(G)＝{a2nbc|n≥0}；L(G)＝{aibcjdk|i,j,k≥1,i=j+k-1}；或者L(G)＝{aj+k-1bcjdk|j,k≥1}；L(G)＝{anbncmdm|m≥0,n≥1}。8.試分別構(gòu)造產(chǎn)生下列語言的文法：（1）{abna|n=0，1，2，3……}（2）{anbn|n=1，2，3，4……}無法轉(zhuǎn)換成正規(guī)表達式，因為a和b的個數(shù)相同（3）{aban|n≥1}可以轉(zhuǎn)換但慎用（4）{anbam|n,m≥1}可以轉(zhuǎn)換但慎用（5）{anbmcp|n,m,p≥0}可以轉(zhuǎn)換（6）{ambmcp|m,p≥0}無法轉(zhuǎn)換（1）G＝{VN，VT，P，S}，VN＝{S，A}，VT＝{a，b}，[可將其看成正規(guī)表達式ab*a，再畫出其狀態(tài)轉(zhuǎn)換圖來求解]P：S∷＝aAa或S∷＝aBA∷＝bA|εB∷＝bB|a（2）G＝{VN，VT，P，S}，VN＝{S}，VT＝{a，b}，P：S∷＝aSb|ε（3）G＝{VN，VT，P，S}，VN＝{S，A}，VT＝{a，b}，P：S∷＝abA或S∷＝Sa|abaA∷＝aA|a（4）G＝{VN，VT，P，S}，VN＝{S，A}，VT＝{a，b}，P：S∷＝aS|abA或S∷＝aS|aAA∷＝bZ或S∷＝aAA∷＝bZ|aAA∷＝aA|aZ∷＝aZ|aZ∷＝aZ|a（5）G＝{VN，VT，P，S}，VN＝{S，A，B，C}，VT＝{a，b，c}，P：S∷＝ABCS∷＝aS|bS|cS|εA∷＝aA|ε或B∷＝bB|εC∷＝cC|ε（6）G＝{VN，VT，P，S}，VN＝{S，A}，VT＝{a，b，c}，P：S∷＝aSbA|εA∷＝cA|ε9.設(shè)文法G規(guī)則為：S∷=ABB∷=a|SbA∷=Aa|bB對下列句型給出推導(dǎo)語法樹，并求出其句型短語，簡單短語和句柄。（1）baabaab(2)bBABb（1）SABAaSbbBABabBaa句型baabaab的短語a,ba,baa,baab,baabaab，簡單短語a，句柄aS（2）ABbBSbAB短語bB,AB,ABb，簡單短語bB,AB，句柄bB10.分別對i+i*i和i+i+i中每一個句子構(gòu)造兩棵語法樹，從而證明下述文法G[<表達式>]是二義的。<表達式>：：=i|(<表達式>)|<表達式><運算符><表達式><運算符>：：=+|-|*|/i+i*i語法樹1：<表達式><表達式><運算符><表達式>i+<表達式><運算符><表達式>i*i語法樹2：<表達式><表達式><運算符><表達式><表達式><運算符><表達式>*ii+i由于句子i+i*i可構(gòu)造兩棵不同的語法樹，所以證明該文法是二義的。(2)i+i+i語法樹1：<表達式><表達式><運算符><表達式>i+<表達式><運算符><表達式>i+i語法樹2：<表達式><表達式><運算符><表達式><表達式><運算符><表達式>+ii+i由于句子i+i+i可構(gòu)造兩棵不同的語法樹，所以證明該文法是二義的。11.證明下述文法是二義的（1）S∷=iSeS|iS|i（2）S∷=A|BA∷=aCbA|aB∷=BCC|aC∷=ba(最簡單的就是a為句型)（1）對于句子iiieii可構(gòu)造兩棵不同的語法樹，所以證明該文法是二義的。SiSeSiSiSiiSiSiSeSiiSi（2）對于句子ababa可構(gòu)造兩棵不同的語法樹，所以證明該文法是二義的。SAaCbAbaaSBBCCababa12.令文法N：：=D|NDD：：=0|1|2|3|4|5|6|7|8|9給出句子0127，34，568的最左推導(dǎo)和最右推導(dǎo)。解：0127的最左推導(dǎo)N=>ND=>NDD=>NDDD=>DDDD=>0DDD=>01DD=>012D=>01270127的最右推導(dǎo)N=>ND=>N7=>ND7=>N27=>ND27=>N127=>D127=>012734的最左推導(dǎo)N=>ND=>DD=>3D=>3434的最右推導(dǎo)N=>ND=>N4=>D4=>34568的最左推導(dǎo)N=>ND=>NDD=>DDD=>5DD=>56D=>568568的最右推導(dǎo)N=>ND=>N8=>ND8=>N68=>D68=>56813.下面文法那些是短語結(jié)構(gòu)文法，上下文有關(guān)文法，上下文無關(guān)文法及正規(guī)文法？（1）S∷=aBB∷=cBB∷=bC∷=c（2）S∷=aBB∷=bCC∷=cC∷=ε（3）S∷=aAbaA∷=aBaA∷=aaAB∷=bA∷=a（4）S∷=aCdaC∷=BaC∷=aaAB∷=b（5）S∷=ABA∷=aB∷=bCB∷=bC∷=c（6）S∷=ABA∷=aB∷=bCC∷=cC∷=ε（7）S∷=aAS∷=εA∷=aAA∷=aBA∷=aB∷=b（8）S∷=aAS∷=εA∷=bAbA∷=a正規(guī)文法：1上下文無關(guān)文法：25678上下文有關(guān)文法：3短語結(jié)構(gòu)文法：414.給出產(chǎn)生下列語言L(G)={W|W∈{0,1}+且W不含相鄰1}的正規(guī)文法。G=({S,A,B},{0,1},P,S)P:S::=0|1|0S|1AA::=0|0S解題思路一：寫出滿足要求的符號串，例如0，1，00，01，10，000，101，010，001等，根據(jù)符號串從左至右的次序畫出狀態(tài)轉(zhuǎn)換圖，然后根據(jù)狀態(tài)轉(zhuǎn)換圖來推導(dǎo)出文法。這將會得到S::=0|1|0S|1A|0Z|1ZA::=0|0S|0Z經(jīng)過分析其中Z為多余狀態(tài)可刪去。SSZ100100A解題思路二：寫出其正規(guī)表達式(0|10)*(10|0|1)【如果僅有(0|10)*的話推導(dǎo)不出1，因為是連接關(guān)系，后面缺了10的話就會以1結(jié)尾，同樣的道理還要推導(dǎo)出0，所以得到此正規(guī)式】，畫出轉(zhuǎn)換系統(tǒng)，然后根據(jù)轉(zhuǎn)換系統(tǒng)來推導(dǎo)出文法。也可以根據(jù)正規(guī)表達式直接寫文法，例如正規(guī)表達式(0|10)*(10|0|1)可以看成是a*b，推導(dǎo)出A::=(0|10)A|10|0|1，即A::=0A|1B|10|0|1，其中B::=0A，但是10此項不符合正規(guī)文法的選項，可以進行改寫從而得到A::=0A|1B|0|1B::=0A|0。15.給出一個產(chǎn)生下列語言L(G)={W|W∈{a,b}*且W中含a的個數(shù)是b個數(shù)兩倍}的上下文無關(guān)文法。（1）文法G=({S,A,B},{a,b},P,S)P:S∷=AAB|ABA|BAA|ε[非終結(jié)符號插位法]A∷=aSB∷=bS或者：（2）S∷=Saab|aSab|aaSb|aabS|Saba|aSba|abSa|abaS|Sbaa|bSaa|baSa|baaS|ε[終結(jié)符號插位法]或者：（3）S∷=aaB|aBa|Baa|ε[非終結(jié)符號與終結(jié)符混合插位法]B∷=SbS16.用擴充的BNF表示以下文法規(guī)則：（1）Z∷=AB|AC|A（2）A∷=BC|BCD|AXZ|AXY（3）S∷=aABb|ab（4）A∷=Aab|ε（1）Z∷=A(B|C|ε)∷=A[B|C]（2）A∷=BC(ε|D)|{X(Z|Y)}∷=BC[D]|{X(Z|Y)}（3）A∷=a((AB|ε)b)∷=a[AB]b（4）A∷={ab|ε}∷={ab}17.判斷題（1）由遞歸文法產(chǎn)生的語言集合一定是無限集合。(√)（2）文法G[S]:S