形式語言與自動機理論-蔣宗禮-第二章參考答案

1、21回答下面的問題： （周期律 02282067）（1）在文法中，終極符號和非終極符號各起什么作用？ü 終結符號是一個文法所產生的語言中句子的中出現(xiàn)的字符，他決定了一個文法的產生語言中字符的范圍。ü 非終結符號又叫做一個語法變量，它表示一個語法范疇，文法中每一個產生式的左部至少要還有一個非終結符號，（二，三型文法要求更嚴，只允許左部為一個非終結符號）他是推導或歸約的核心。（2）文法的語法范疇有什么意義？開始符號所對應的語法范疇有什么特殊意義？ü 文法的非終結符號A所對應的語法范疇代表著一個集合L（A），此集合由文法產生式中關于A的產生式推導實現(xiàn)的ü 開始

2、符號所對應的語法范疇則為文法G = V，T，P，S所產生的語言L（G）=（3）在文法中，除了的變量可以對應一個終極符號行的集合外，按照類似的對應方法，一個字符串也可以對應一個終極符號行集合，這個集合表達什么意義？ü 字符串對應的終極符號行集合表示這個字符串所能推導到的終極字符串集合，為某個句型的語言。（4）文法中的歸約和推導有什么不同？ü 推導：文法G = V，T，P，S，如果則稱在G中推導出了。ü 歸約：文法G = V，T，P，S，如果則稱在G中歸約到。ü 這他們的定義，我個人理解兩個概念從不同角度看待文法中的產生式，推導是自上而下（從產生式的左邊到右

3、邊），而歸約是自下而上（從產生式的右邊到左邊），體現(xiàn)到具體實際中，如編譯中語法分析時語法樹的建立，遞歸下降，LL（1）等分析法采用自開始符號向下推導識別輸入代碼生成語法樹，對應的LR（1），LALR等分析法則是采用自輸入代碼（相當于文法中語言的句子）自底向上歸約到開始符號建立語法樹，各有優(yōu)劣。（5）為什么要求定義語言的字母表上的語言為一個非空有窮集合？ü 非空：根據(jù)字母表冪的定義：為字母表中個字符組成的。這樣，當字母表中沒有字符的情況，字母表也有一個元素，字母表為空就沒有意義，而且，如果字母表為空，將無法定義其上的語言，使得理論體系不嚴密。ü 有窮：我們將語言抽象成形式語言

4、的目的就是為了有窮的表示無限的語言，在此基礎上我們才定義了字母表和語言，如果字母表為無窮的，他就違背了我們研究問題的初衷，這也使得研究失去意義（6）任意給定一個字母表，該字母表上的語言都具有有窮描述嗎？為什么？ü 錯誤，因為一個字母表上有不可數(shù)無窮多個語言，而有窮表示只可能是可數(shù)無窮多個，又因為不可數(shù)無窮集和可數(shù)無窮集不是一一對應的，所以存在這樣的語言，他不存在有窮表示。（7）請總結一下，在構造文法時，可以從哪幾個方面入手？ü 我們可以將其類比于軟件工程中的概念:-)ü 首先，也是最重要的一點，需求分析，我們需要知道需要構造的語言的特點，具體表現(xiàn)形式，以及一些需要

5、注意的細節(jié)，通過一些特例提煉特點。ü 其次，概要設計，將語言從具體中抽象到符號上，按照其特性將其劃分類別。ü 再次，詳細設計，將每一部分抽象的成果具體化，將所有細節(jié)符號化ü 再次，編碼，將詳細設計的結果用文法符號的語言表示出來ü 最后，測試，找出邊緣數(shù)據(jù)，特殊數(shù)據(jù)進行測試。（8）按照文法的喬姆斯基體系，文法被分為幾類？各有什么樣的特點？分為四類：ü 文法G = V，T，P，S，對應的（）則為型文法或短語結果文法。ü 如果對于，均有成立，則稱為型文法或上下文有關文法，對應的（）稱為型語言。ü 如果對于，均有成立，且成立，則稱為

6、型文法，或上下文無關文法，對應的（）為型語言。ü 如果對于，所有均有：成立，其中則稱為型文法，或正則文法，對應的（）稱型語言。（9）什么叫左線性文法？什么叫右線性文法？什么叫線性文法ü 文法G = V，T，P，S，如果對于，所有均有：成立，則稱為線性文法。ü 文法G = V，T，P，S，如果對于，所有均有：成立，其中則稱為右線性文法。ü 文法G = V，T，P，S，如果對于，所有均有：成立，其中則稱為左線性文法。（10）既然已經定義2-10中允許RL包含空語句，那么定理2-6和定理2-7還有什么意義？ü 此為定義與定理的區(qū)別，定義2-10是針對

7、文法是的情況下，定義其產生式加上后仍為，的語言仍為，而定理2-6和定理2-7針對的前提條件是如果為，他們都是通過定義2-10證明得到的，可以在以后的推論中直接應用的。*2. 設L = 0n | n 1 ,試構造滿足要求的文法G.(1) G是RG.(2) G是CFG, 但不是RG.(3) G是CSG, 但不是CFG.(4) G是短語結構文法,但不是CSG.解答：1：S0|0S2：S0|0S|SS3：S0|0S|AS ASSA AS0A 0AS0 0AS004：S0|0S|AS ASSA|ABB ABBAS ABA| *3.設文法G的產生式集如下，試給出句子id+id*id的兩個不同的推導和兩個不

8、同的歸約 Eid|c|+E|-E|E+E|E-E|E*E|E/E|E*E|Fun(E) （褚穎娜 02282072）推導：(1)E=>E+E=>E+E*E=>E+E*id=> E+id*id=>id+id*id(2)E=>E*E=>E*id=>E+E*id=>E+id*id=>id+id*id歸約：(1)id+id*id<= E+id*id<= E+E*id<= E+E*E <=E+E<=E(2)id+id*id<= E+id*id<= E+E*id<=E*id<= E*E<

9、=E*2.4 設文法G的產生式集如下，試給出句子aaabbbccc的至少兩個不同的推導和至少兩個不同的歸約 （02282081劉秋雯）bBbbCBBCbCbccCcc解：推導一： SaBC|aSBC aBab S=>aSBC=>aaSBCBC=>aaaBCBCBC=>aaabCBCBC=>aaabBCCBC=>aaabbCCBC=>aaabbCBCC=>aaabbBCCC=>aaabbbCCC=>aaabbbcCC=>aaabbbccc 推導二： S=>aSBC=>aaSBCBC=>aaaBCBCBC =>

10、;aaaBBCCBC =>aaaBBCBCC =>aaabbCBCC=>aaabbBCCC=>aaabbbCCC=>aaabbbcCC=>aaabbbccc 歸約一、歸約二分別為推導一和推導二的逆過程*5 句子abeebbeeba的一個推導如下： （陳偉芳 學號？）S=>aAa 使用產生式SàaAa =>aSSa 使用產生式AàSS =>abAbSa 使用產生式SàbAb =>abSSbSa 使用產生式AàSS =>abeSbSa 使用產生式Sàe =>abeebSa 使用

11、產生式Sàe =>abeebbAba 使用產生式SàbAb =>abeebbSSba 使用產生式AàSS =>abeebbeSba 使用產生式Sàe =>abeebbeeba 使用產生式Sàe不能給出abeebbeeb的歸約，因為由文法G中產生式推出的句子只有三種情況：頭尾都是a,頭尾都是b，或者只有一個e，而abeebbeeb上面三個條件都不符合，所以它不是文法G的一個句子，當然也就不能給出它的一個歸約了。*2.6 設文法G的產生式集如下,請給出G的每個語法范疇代表的集合.SaSa|aaSaa|aAaAbA|bbbA|

12、bBBcB|cCCccC|DDDdD|d解:set(D)=d+set(C)= c2n dm| m2 n0set(B)= c n d m |m2 n1set(A)= bpcndm | p1, m2, n1set(S)= aqbpcndmaq| p1 ,m2, n1, q1*7給定如下文法，請用自然語言描述它們定義的語言。 （吳賢珺 02282047） AaaAaaB BBccD#cc DbbbD#解：該語言由四部分組成：第一部分是偶數(shù)個a（至少有兩個），第二部分是3的倍數(shù)個b（可以是0個），第三部分是兩個“#”號，第四部分是偶數(shù)個c（至少有兩個）。 A0B1B2B B0C1C2C C0D1D2D

13、012D0B1B2B解：該語言的句子是字母表0,1,2上所有長度為3的倍數(shù)的字符串，且非空。 A0B1B2BB0C1B2BC0E1D2D012D0C1B2BE0E1D2D012解：觀察發(fā)現(xiàn)C和E所對應產生式右部是相同的。所以將文法化簡成如下的形式：A0B1B2BB0C1B2BC0C1D2D012D0C1B2B作出狀態(tài)圖如下：ABCD0, 1, 21, 2001, 21, 200, 1, 2F 可以看出從初始狀態(tài)A到終態(tài)F，至少要經過ABCF的過程，所以字符串的長度至少為3。而且，到F只能經過C，如果到達C后走其它的路徑，那么所經過的弧上的字符串都是以0為結尾，也就是要回到C，最后一個字符一定是

14、0。這樣，該文法所確定的語言就是所有倒數(shù)第2個字符是0的串。 SaBbAAaaSBAABbbSABB解：由于該文法所確定的語言一時不易看出，可以先考慮簡單的形式： SaBbAAaaSBbbS不難看出，該文法所確定的語言為所有由ab和ba組成的串，且非空。這些串有一個特點，就是a和b的個數(shù)相等。然后，把產生式ABAA 和BABB加回到原來的文法中，并且可以把這兩個產生式看成是在左部的符號前分別加上串BA和AB。不妨把它們看成一個符號C和D。這樣原文法可以改造成如下形式：SaBbAAaaSCABbbSDBCBADAB發(fā)現(xiàn)插入的C和D所導入的A和B是成對的，原文法所確定的語言可能就是字母表a,b上所

15、有含有相同個a和b的字符串，且非空。從上面簡單形式的文法中已經看到，它所確定的字符串比a和b個數(shù)相同的所有串少的只是多個a或b連續(xù)的情況。而加上產生式ABAA 和BABB后則剛好滿足。例如：由S推出aB后，在B前“插入”D（即AB），可由AB中的A推出a，就得到aaBB，如此類推，最終可得該文法所接受的語言為：字母表a,b上所有a和b個數(shù)相等的非空字符串。*8設=0,1,請給出上的下列語言的文法(1)所有以0開頭的串 S0A|0 A0|1|0A|1A(2)所有以0開頭以1結尾的串 S0A A1|0A|1A(3)所有以11開頭以11結尾的串 S11A|11 A11|0A|1A(4)所有最多有一對

16、連續(xù)的0或者最多有一對連續(xù)的1 1：x中既沒有成對的0，也沒有成對的1 2：x有一對連續(xù)的0 3： x有一對連續(xù)的1 4：x中既有一對連續(xù)的0，也有一對連續(xù)的1 SA|B|C|D A|A|A” A 0|01|01A A” 1|10|10A” BB00B” B 1|01|1B|01B B” 1|10|1B”10B” CC11C” C 0|10|0C|10C C” 0|01|0C”|01C” DE00F11H|P11G00K E1|1E|E E 01E|E F|10|10F / F 以1開頭，以0結尾；不含連續(xù)0和連續(xù)1 H0|H0|H H 01|01H P0|0P|P P 10P|10 G|01

17、|01G / G 以0開頭，以1結尾；不含連續(xù)0和連續(xù)1 K1|K1|K K 10|10K (5) 所有最多有一對連續(xù)的0而且最多有一對連續(xù)的1 1：x中既沒有成對的0，也沒有成對的1 2：x只有一對連續(xù)的0，沒有連續(xù)的1 3：y只有一對連續(xù)的1，沒有連續(xù)的0 4：x中既有一對連續(xù)的0，也有一對連續(xù)的1 SA|B|C|D A|A|A” A 0|01|01A A” 1|10|10A” BB00B” B |1|01|01B|1 B / B是不含連續(xù)0，也不含連續(xù)1的串 B 01|01 B B” |1|10|10B” / B”是不含連續(xù)0，也不含連續(xù)1的串 B” 10|10 B” CC11C” /

18、C是不含連續(xù)1，也不含連續(xù)0的串 C |0|10|0C”|10C” C” 10|10 C” C” |0|01|01C” / C”是不含連續(xù)1，也不含連續(xù)0的串 C” 01|01 C” DE00F11H|P11G00K E1|1E|E E 01E|E F|10|10F / F 以1開頭，以0結尾；不含連續(xù)0和連續(xù)1 H0|H0|H H 01|01H P0|0P|P P 10P|10 G|01|01G / G 以0開頭，以1結尾；不含連續(xù)0和連續(xù)1 K1|K1|K K 10|10K (6)所有長度為偶數(shù)的串 S01|10|00|11|01S|10S|00S|11S(7)所有包含子串01011的串

19、SX01011Y X|0X|1X Y|0Y|1Y(8)所有含有3個連續(xù)0的串 SX000Y X|0X|1X Y|0Y|1Y*2.9 設，構造下列語言的文法。 (1) 。 解答：。 (2) 。 解答：。 (3) 。 解答： S aAB|aSABBAABaBabbBbbbAbaaAaa (4) 。 解答：。 (5) 。 解答：。 (6) 。 解答： 。 (7) 。 解答：。 (8) 。 解答： 。*第10題參見下題：11、給定RG試分別構造滿足下列要求的RG G，并證明你的結論。解：P=S|S1P1SSS|S1P1證明略。解：P=S|S1P1SS|S1P1證明略。*12設文法G有如下產生式： （吳

20、賢珺 02282047） SaBbAAaaSbAABbbSaBB證明L(G)中含有相同個數(shù)的a和b，且非空。證：觀察發(fā)現(xiàn)A的產生式AbAA中的bA可以用S來代替，同樣B的產生式BaBB中的aB也可以用S代替。這樣原來的文法可以化為如下的形式： SaBbAAaaSSABbbSSB進一步地，可以把產生式AaS中的S代換，把文法化為如下的形式： SaBbAAaaaBabASABbbaBbbASB下面，我們就對字符串的長度施歸納，同時證明以下三個命題成立。 iff中含有相同個數(shù)的a和b，且非空。 iff中含有a的個數(shù)比b的個數(shù)恰好多一個。 iff中含有a的個數(shù)比b的個數(shù)恰好少一個。第一步，由于只有A和B可以直接推出終結符，當?shù)拈L度為1時，直接用A推出a或直接用B推出b。直接用A推出a時，中a的長度為1，b的長度為0，含有a的個數(shù)比b的個數(shù)恰好多一個。 直接用B推出b時，