形式語言與自動(dòng)機(jī)理論-蔣宗禮-第二章參考答案.doc

《形式語言與自動(dòng)機(jī)理論-蔣宗禮-第二章參考答案.doc》由會(huì)員分享，可在線閱讀，更多相關(guān)《形式語言與自動(dòng)機(jī)理論-蔣宗禮-第二章參考答案.doc（13頁珍藏版）》請?jiān)谘b配圖網(wǎng)上搜索。

2．1回答下面的問題： （周期律 02282067） （1）在文法中，終極符號(hào)和非終極符號(hào)各起什么作用？ 終結(jié)符號(hào)是一個(gè)文法所產(chǎn)生的語言中句子的中出現(xiàn)的字符，他決定了一個(gè)文法的產(chǎn)生語言中字符的范圍。 非終結(jié)符號(hào)又叫做一個(gè)語法變量，它表示一個(gè)語法范疇，文法中每一個(gè)產(chǎn)生式的左部至少要還有一個(gè)非終結(jié)符號(hào)，（二，三型文法要求更嚴(yán)，只允許左部為一個(gè)非終結(jié)符號(hào)）他是推導(dǎo)或歸約的核心。 （2）文法的語法范疇有什么意義？開始符號(hào)所對應(yīng)的語法范疇有什么特殊意義？ 文法的非終結(jié)符號(hào)A所對應(yīng)的語法范疇代表著一個(gè)集合L（A），此集合由文法產(chǎn)生式中關(guān)于A的產(chǎn)生式推導(dǎo)實(shí)現(xiàn)的 開始符號(hào)所對應(yīng)的語法范疇則為文法G = {V，T，P，S}所產(chǎn)生的語言L（G）={} （3）在文法中，除了的變量可以對應(yīng)一個(gè)終極符號(hào)行的集合外，按照類似的對應(yīng)方法，一個(gè)字符串也可以對應(yīng)一個(gè)終極符號(hào)行集合，這個(gè)集合表達(dá)什么意義？ 字符串對應(yīng)的終極符號(hào)行集合表示這個(gè)字符串所能推導(dǎo)到的終極字符串集合，為某個(gè)句型的語言。 （4）文法中的歸約和推導(dǎo)有什么不同？ 推導(dǎo)：文法G = {V，T，P，S}，如果則稱在G中推導(dǎo)出了。 歸約：文法G = {V，T，P，S}，如果則稱在G中歸約到。 這他們的定義，我個(gè)人理解兩個(gè)概念從不同角度看待文法中的產(chǎn)生式，推導(dǎo)是自上而下（從產(chǎn)生式的左邊到右邊），而歸約是自下而上（從產(chǎn)生式的右邊到左邊），體現(xiàn)到具體實(shí)際中，如編譯中語法分析時(shí)語法樹的建立，遞歸下降，LL（1）等分析法采用自開始符號(hào)向下推導(dǎo)識(shí)別輸入代碼生成語法樹，對應(yīng)的LR（1），LALR等分析法則是采用自輸入代碼（相當(dāng)于文法中語言的句子）自底向上歸約到開始符號(hào)建立語法樹，各有優(yōu)劣。 （5）為什么要求定義語言的字母表上的語言為一個(gè)非空有窮集合？ 非空：根據(jù)字母表冪的定義：為字母表中０個(gè)字符組成的。這樣，當(dāng)字母表中沒有字符的情況，字母表也有一個(gè)元素，字母表為空就沒有意義，而且，如果字母表為空，將無法定義其上的語言，使得理論體系不嚴(yán)密。 有窮：我們將語言抽象成形式語言的目的就是為了有窮的表示無限的語言，在此基礎(chǔ)上我們才定義了字母表和語言，如果字母表為無窮的，他就違背了我們研究問題的初衷，這也使得研究失去意義 （6）任意給定一個(gè)字母表，該字母表上的語言都具有有窮描述嗎？為什么？ 錯(cuò)誤，因?yàn)橐粋€(gè)字母表上有不可數(shù)無窮多個(gè)語言，而有窮表示只可能是可數(shù)無窮多個(gè)，又因?yàn)椴豢蓴?shù)無窮集和可數(shù)無窮集不是一一對應(yīng)的，所以存在這樣的語言，他不存在有窮表示。 （7）請總結(jié)一下，在構(gòu)造文法時(shí)，可以從哪幾個(gè)方面入手？ 我們可以將其類比于軟件工程中的概念:-) 首先，也是最重要的一點(diǎn)，需求分析，我們需要知道需要構(gòu)造的語言的特點(diǎn)，具體表現(xiàn)形式，以及一些需要注意的細(xì)節(jié)，通過一些特例提煉特點(diǎn)。 其次，概要設(shè)計(jì)，將語言從具體中抽象到符號(hào)上，按照其特性將其劃分類別。 再次，詳細(xì)設(shè)計(jì)，將每一部分抽象的成果具體化，將所有細(xì)節(jié)符號(hào)化 再次，編碼，將詳細(xì)設(shè)計(jì)的結(jié)果用文法符號(hào)的語言表示出來 最后，測試，找出邊緣數(shù)據(jù)，特殊數(shù)據(jù)進(jìn)行測試。 （8）按照文法的喬姆斯基體系，文法被分為幾類？各有什么樣的特點(diǎn)？ 分為四類： 文法G = {V，T，P，S}，對應(yīng)的Ｌ（Ｇ）則為０型文法或短語結(jié)果文法。 如果對于，均有成立，則稱Ｇ為１型文法或上下文有關(guān)文法，對應(yīng)的Ｌ（Ｇ）稱為１型語言。 如果對于，均有成立，且成立，則稱Ｇ為２型文法，或上下文無關(guān)文法，對應(yīng)的Ｌ（Ｇ）為２型語言。 如果對于，所有均有：成立，其中則稱Ｇ為３型文法，或正則文法，對應(yīng)的Ｌ（Ｇ）稱３型語言。 （9）什么叫左線性文法？什么叫右線性文法？什么叫線性文法 文法G = {V，T，P，S}，如果對于，所有均有：成立，則稱Ｇ為線性文法。 文法G = {V，T，P，S}，如果對于，所有均有：成立，其中則稱Ｇ為右線性文法。 文法G = {V，T，P，S}，如果對于，所有均有：成立，其中則稱Ｇ為左線性文法。 （10）既然已經(jīng)定義2-10中允許RL包含空語句，那么定理2-6和定理2-7還有什么意義？ 此為定義與定理的區(qū)別，定義2-10是針對文法Ｇ是ＲＧ的情況下，定義其產(chǎn)生式加上后仍為ＲＧ，Ｇ的語言仍為ＲＬ，而定理2-6和定理2-7針對的前提條件是如果Ｌ為ＲＬ，他們都是通過定義2-10證明得到的，可以在以后的推論中直接應(yīng)用的。 ******************************************************************************* 2. 設(shè)L = { 0n | n ≥ 1 },試構(gòu)造滿足要求的文法G. (1) G是RG. (2) G是CFG, 但不是RG. (3) G是CSG, 但不是CFG. (4) G是短語結(jié)構(gòu)文法,但不是CSG. 解答： 1：S→0|0S 2：S→0|0S|SS 3：S→0|0S|AS AS→SA AS→0A 0A→S0 0AS→00 4：S→0|0S|AS AS→SA|ABB ABB→AS AB→A|ε ******************************************************************************* 3.設(shè)文法G的產(chǎn)生式集如下，試給出句子id+id*id的兩個(gè)不同的推導(dǎo)和兩個(gè)不同的歸約 E→id|c|+E|-E|E+E|E-E|E*E|E/E|E**E|Fun(E) （褚穎娜 02282072） 推導(dǎo)： (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<=E ****************************************************************************** 2.4 設(shè)文法G的產(chǎn)生式集如下，試給出句子aaabbbccc的至少兩個(gè)不同的推導(dǎo)和至少兩個(gè)不同的歸約 （02282081劉秋雯） bB→bb CB→BC bC→bc cC→cc 解：推導(dǎo)一： S→aBC|aSBC aB→ab S=>aSBC =>aaSBCBC =>aaaBCBCBC =>aaabCBCBC =>aaabBCCBC =>aaabbCCBC =>aaabbCBCC =>aaabbBCCC =>aaabbbCCC =>aaabbbcCC =>aaabbbccc 推導(dǎo)二： S=>aSBC =>aaSBCBC =>aaaBCBCBC =>aaaBBCCBC =>aaaBBCBCC =>aaabbCBCC =>aaabbBCCC =>aaabbbCCC =>aaabbbcCC =>aaabbbccc 歸約一、歸約二分別為推導(dǎo)一和推導(dǎo)二的逆過程 ******************************************************************************* 5 句子abeebbeeba的一個(gè)推導(dǎo)如下： （陳偉芳 學(xué)號(hào)？？） S=>aAa 使用產(chǎn)生式SaAa =>aSSa 使用產(chǎn)生式ASS =>abAbSa 使用產(chǎn)生式SbAb =>abSSbSa 使用產(chǎn)生式ASS =>abeSbSa 使用產(chǎn)生式Se =>abeebSa 使用產(chǎn)生式Se =>abeebbAba 使用產(chǎn)生式SbAb =>abeebbSSba 使用產(chǎn)生式ASS =>abeebbeSba 使用產(chǎn)生式Se =>abeebbeeba 使用產(chǎn)生式Se 不能給出abeebbeeb的歸約，因?yàn)橛晌姆℅中產(chǎn)生式推出的句子只有三種情況：頭尾都是a,頭尾都是b，或者只有一個(gè)e，而abeebbeeb上面三個(gè)條件都不符合，所以它不是文法G的一個(gè)句子，當(dāng)然也就不能給出它的一個(gè)歸約了。******************************************************************************* 2.6 設(shè)文法G的產(chǎn)生式集如下,請給出G的每個(gè)語法范疇代表的集合. S→aSa|aaSaa|aAa A→bA|bbbA|bB B→cB|cC C→ccC|DD D→dD|d 解: set(D)=efzymgh+ set(C)={ c2n dm| m≥2 n≥0} set(B)={ c n d m |m≥2 n≥1} set(A)={ bpcndm | p≥1, m≥2, n≥1} set(S)={ aqbpcndmaq| p≥1 ,m≥2, n≥1, q≥1} ******************************************************************************* 7．給定如下文法，請用自然語言描述它們定義的語言。 （吳賢珺 02282047） ⑴ A→aaA│aaB B→Bcc│D#cc D→bbbD│# 解：該語言由四部分組成：第一部分是偶數(shù)個(gè)a（至少有兩個(gè)），第二部分是3的倍數(shù)個(gè)b（可以是0個(gè)），第三部分是兩個(gè)“#”號(hào)，第四部分是偶數(shù)個(gè)c（至少有兩個(gè)）。 ⑵ A→0B│1B│2B B→0C│1C│2C C→0D│1D│2D│0│1│2 D→0B│1B│2B 解：該語言的句子是字母表∑＝{0,1,2}上所有長度為3的倍數(shù)的字符串，且非空。 ⑶ A→0B│1B│2B B→0C│1B│2B C→0E│1D│2D│0│1│2 D→0C│1B│2B E→0E│1D│2D│0│1│2 解：觀察發(fā)現(xiàn)C和E所對應(yīng)產(chǎn)生式右部是相同的。所以將文法化簡成如下的形式： A→0B│1B│2B B→0C│1B│2B C→0C│1D│2D│0│1│2 D→0C│1B│2B 作出狀態(tài)圖如下： A B C D 0, 1, 2 1, 2 0 0 1, 2 1, 2 0 0, 1, 2 F 可以看出從初始狀態(tài)A到終態(tài)F，至少要經(jīng)過A→B→C→F的過程，所以字符串的長度至少為3。而且，到F只能經(jīng)過C，如果到達(dá)C后走其它的路徑，那么所經(jīng)過的弧上的字符串都是以0為結(jié)尾，也就是要回到C，最后一個(gè)字符一定是0。這樣，該文法所確定的語言就是所有倒數(shù)第2個(gè)字符是0的串。 ⑷ S→aB│bA A→a│aS│BAA B→b│bS│ABB 解：由于該文法所確定的語言一時(shí)不易看出，可以先考慮簡單的形式： S→aB│bA A→a│aS B→b│bS 不難看出，該文法所確定的語言為所有由ab和ba組成的串，且非空。這些串有一個(gè)特點(diǎn)，就是a和b的個(gè)數(shù)相等。然后，把產(chǎn)生式A→BAA 和B→ABB加回到原來的文法中，并且可以把這兩個(gè)產(chǎn)生式看成是在左部的符號(hào)前分別加上串BA和AB。不妨把它們看成一個(gè)符號(hào)C和D。這樣原文法可以改造成如下形式： S→aB│bA A→a│aS│CA B→b│bS│DB C→BA D→AB 發(fā)現(xiàn)插入的C和D所導(dǎo)入的A和B是成對的，原文法所確定的語言可能就是字母表∑＝{a,b}上所有含有相同個(gè)a和b的字符串，且非空。從上面簡單形式的文法中已經(jīng)看到，它所確定的字符串比a和b個(gè)數(shù)相同的所有串少的只是多個(gè)a或b連續(xù)的情況。而加上產(chǎn)生式A→BAA 和B→ABB后則剛好滿足。 例如：由S推出aB后，在B前“插入”D（即AB），可由AB中的A推出a，就得到aaBB，如此類推，最終可得該文法所接受的語言為：字母表∑＝{a,b}上所有a和b個(gè)數(shù)相等的非空字符串。 ******************************************************************************* 8．設(shè)∑={0,1},請給出∑上的下列語言的文法 (1)所有以0開頭的串 S→0A|0 A→0|1||0A|1A (2)所有以0開頭以1結(jié)尾的串 S→0A A→1|0A|1A (3)所有以11開頭以11結(jié)尾的串 S→11A|11 A→11|0A|1A (4)所有最多有一對連續(xù)的0或者最多有一對連續(xù)的1 1：x中既沒有成對的0，也沒有成對的1 2：x有一對連續(xù)的0 3： x有一對連續(xù)的1 4：x中既有一對連續(xù)的0，也有一對連續(xù)的1 S→A|B|C|D A→ε|A’|A” A’ →0|01|01A’ A” →1|10|10A” B→B’00B” B’ →1|01|1B’|01B’ B” →1|10|1B”10B” C→C’11C” C’ →0|10|0C’|10C’ C” →0|01|0C”|01C” D→E00F11H|P11G00K E→1|1E’|E’ E’ →01E’|E’ F→ε|10|10F // F 以1開頭，以0結(jié)尾；不含連續(xù)0和連續(xù)1 H→0|H’0|H’ H’ →01|01H’ P→0|0P’|P’ P’ →10P’|10 G→ε|01|01G // G 以0開頭，以1結(jié)尾；不含連續(xù)0和連續(xù)1 K→1|K’1|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 S→A|B|C|D A→ε|A’|A” A’ →0|01|01A’ A” →1|10|10A” B→B’00B”’ 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”” C→C’11C”’ // 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”” D→E00F11H|P11G00K E→1|1E’|E’ E’ →01E’|E’ F→ε|10|10F // F 以1開頭，以0結(jié)尾；不含連續(xù)0和連續(xù)1 H→0|H’0|H’ H’ →01|01H’ P→0|0P’|P’ P’ →10P’|10 G→ε|01|01G // G 以0開頭，以1結(jié)尾；不含連續(xù)0和連續(xù)1 K→1|K’1|K’ K’ →10|10K’ (6)所有長度為偶數(shù)的串 S→01|10|00|11|01S|10S|00S|11S (7)所有包含子串01011的串 S→X01011Y X→ε|0X|1X Y→ε|0Y|1Y (8)所有含有3個(gè)連續(xù)0的串 S→X000Y X→ε|0X|1X Y→ε|0Y|1Y ******************************************************************************* 2.9 設(shè)，構(gòu)造下列語言的文法。 (1) 。 解答：。 (2) 。 解答：。 (3) 。 解答： S →aAB|aSAB BA→AB aB→ab bB→bb bA→ba aA→aa (4) 。 解答：。 (5) 。 解答：。 (6) 。 解答： 。 (7) 。 解答：。 (8) 。 解答： 。 ******************************************************************************* 第10題參見下題： 11、給定RG 試分別構(gòu)造滿足下列要求的RG G，并證明你的結(jié)論。 解： P={S→α|S1→α∈P1}∪{S→ε}∪{S→αS|S1→α∈P1} 證明略。 解： P={S→α|S1→α∈P1}∪{S→αS|S1→α∈P1} 證明略。 ******************************************************************************* 12．設(shè)文法G有如下產(chǎn)生式： （吳賢珺 02282047） S→aB│bA A→a│aS│bAA B→b│bS│aBB 證明L(G)＝{ω│ω中含有相同個(gè)數(shù)的a和b，且ω非空}。 證：觀察發(fā)現(xiàn)A的產(chǎn)生式A→bAA中的bA可以用S來代替，同樣B的產(chǎn)生式B→aBB中的aB也可以用S代替。這樣原來的文法可以化為如下的形式： S→aB│bA A→a│aS│SA B→b│bS│SB 進(jìn)一步地，可以把產(chǎn)生式A→aS中的S代換，把文法化為如下的形式： S→aB│bA A→a│aaB│abA│SA B→b│baB│bbA│SB 下面，我們就對字符串ω的長度施歸納，同時(shí)證明以下三個(gè)命題成立。 ⑴ ωiffω中含有相同個(gè)數(shù)的a和b，且ω非空。 ⑵ ωiffω中含有a的個(gè)數(shù)比b的個(gè)數(shù)恰好多一個(gè)。 ⑶ ωiffω中含有a的個(gè)數(shù)比b的個(gè)數(shù)恰好少一個(gè)。 第一步，由于只有A和B可以直接推出終結(jié)符，當(dāng)ω的長度為1時(shí)，直接用A推出a或直接用B推出b。 直接用A推出a時(shí)，ω中a的長度為1，b的長度為0，含有a的個(gè)數(shù)比b的個(gè)數(shù)恰好多一個(gè)。 直接用B推出b時(shí)，b的長度為1，a的長度為0，ω中含有a的個(gè)數(shù)比b的個(gè)數(shù)恰好少一個(gè)。 這樣，由S→aB│bA，知S推出的最短串，分別是ab和bb，其長度是2，并且a和b的個(gè)數(shù)相等。 第二步，假設(shè)上面的三個(gè)命題對長度為x的串成立。對S，x＝2n(n≥1)；對A和B，x＝2n＋1(n≥0)。我們可以看到，由A或B推出的串長度如果要變長的話，必須把A或B用其除A→a或B→b之外的產(chǎn)生式代替。 i）.考慮代替A的情形。 若A用aaB代替，由假設(shè)B中a的個(gè)數(shù)比b的個(gè)數(shù)恰好少一個(gè)，則aaB中a的個(gè)數(shù)比b的個(gè)數(shù)恰好多一個(gè)。 若A用abA代替，由假設(shè)A中a的個(gè)數(shù)比b的個(gè)數(shù)恰好多一個(gè)，則abA中a的個(gè)數(shù)比b的個(gè)數(shù)恰好多一個(gè)。 若A用SA代替，由假設(shè)A中a的個(gè)數(shù)比b的個(gè)數(shù)恰好多一個(gè)，而S中a和b的個(gè)數(shù)相等，則SA中a的個(gè)數(shù)仍然比b的個(gè)數(shù)恰好多一個(gè)。 ii）.考慮代替B情形。 若B用baB代替，由假設(shè)B中a的個(gè)數(shù)比b的個(gè)數(shù)恰好少一個(gè)，則baB中a的個(gè)數(shù)比b的個(gè)數(shù)也恰好少一個(gè)。 若B用bbA代替，由假設(shè)A中a的個(gè)數(shù)比b的個(gè)數(shù)恰好多一個(gè)，則bbA中a的個(gè)數(shù)比b的個(gè)數(shù)恰好少一個(gè)。 若B用SB代替，由假設(shè)B中含有a的個(gè)數(shù)比b的個(gè)數(shù)恰好少一個(gè)，而S中a和b的個(gè)數(shù)相等，則SB中a的個(gè)數(shù)仍然比b的個(gè)數(shù)恰好少一個(gè)。 這樣，命題 ωiffω中含有a的個(gè)數(shù)比b的個(gè)數(shù)恰好多一個(gè)。 ωiffω中含有a的個(gè)數(shù)比b的個(gè)數(shù)恰好少一個(gè)。 就得到了證明。又由于S的產(chǎn)生式只有S→aB│bA，由以上兩個(gè)命題，顯然有命題 ωiffω中含有相同個(gè)數(shù)的a和b，且ω非空。 成立。