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

形式語言與自動(dòng)機(jī)理論-蔣宗禮-第二章參考答案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)所對(duì)應(yīng)的語法范疇有什么特殊意義？文法的非終結(jié)符號(hào)A所對(duì)應(yīng)的語法范疇代表著一個(gè)集合L（A），此集合由文法產(chǎn)生式中關(guān)于A的產(chǎn)生式推導(dǎo)實(shí)現(xiàn)的開始符號(hào)所對(duì)應(yīng)的語法范疇則為文法G={V，T，P，S}所產(chǎn)生的語言L（G）={wSTww**|?∈且}（3）在文法中，除了的變量可以對(duì)應(yīng)一個(gè)終極符號(hào)行的集合外，按照類似的對(duì)應(yīng)方法，一個(gè)字符串也可以對(duì)應(yīng)一個(gè)終極符號(hào)行集合，這個(gè)集合表達(dá)什么意義？字符串對(duì)應(yīng)的終極符號(hào)行集合表示這個(gè)字符串所能推導(dǎo)到的終極字符串集合，為某個(gè)句型的語言。（4）文法中的歸約和推導(dǎo)有什么不同？推導(dǎo)：文法G={V，T，P，S}，如果,)(,,*YTVP∈∈→δγβα則稱γαδ在G中推導(dǎo)出了γβδ。歸約：文法G={V，T，P，S}，如果,)(,,*YTVP∈∈→δγβα則稱γβδ在G中歸約到γαδ。這他們的定義，我個(gè)人理解兩個(gè)概念從不同角度看待文法中的產(chǎn)生式，推導(dǎo)是自上而下（從產(chǎn)生式的左邊到右邊），而歸約是自下而上（從產(chǎn)生式的右邊到左邊），體現(xiàn)到具體實(shí)際中，如編譯中語法分析時(shí)語法樹的建立，遞歸下降，LL（1）等分析法采用自開始符號(hào)向下推導(dǎo)識(shí)別輸入代碼生成語法樹，對(duì)應(yīng)的LR（1），LALR等分析法則是采用自輸入代碼（相當(dāng)于文法中語言的句子）自底向上歸約到開始符號(hào)建立語法樹，各有優(yōu)劣。（5）為什么要求定義語言的字母表上的語言為一個(gè)非空有窮集合？非空：根據(jù)字母表冪的定義：εε,}{0∑=為字母表中０個(gè)字符組成的。這樣，當(dāng)字母表中沒有字符的情況，字母表也有一個(gè)元素，字母表為空就沒有意義，而且，如果字母表為空，將無法定義其上的語言，使得理論體系不嚴(yán)密。有窮：我們將語言抽象成形式語言的目的就是為了有窮的表示無限的語言，在此基礎(chǔ)上我們才定義了字母表和語言，如果字母表為無窮的，他就違背了我們研究問題的初衷，這也使得研究失去意義（6）任意給定一個(gè)字母表∑，該字母表上的語言都具有有窮描述嗎？為什么？錯(cuò)誤，因?yàn)橐粋€(gè)字母表上有不可數(shù)無窮多個(gè)語言，而有窮表示只可能是可數(shù)無窮多個(gè)，又因?yàn)椴豢蓴?shù)無窮集和可數(shù)無窮集不是一一對(duì)應(yīng)的，所以存在這樣的語言，他不存在有窮表示。（7）請(qǐng)總結(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}，對(duì)應(yīng)的Ｌ（Ｇ）則為０型文法或短語結(jié)果文法。如果對(duì)于P∈→?βα，均有αβ≥成立，則稱Ｇ為１型文法或上下文有關(guān)文法，對(duì)應(yīng)的Ｌ（Ｇ）稱為１型語言。如果對(duì)于P∈→?βα，均有αβ≥成立，且V∈α成立，則稱Ｇ為２型文法，或上下文無關(guān)文法，對(duì)應(yīng)的Ｌ（Ｇ）為２型語言。如果對(duì)于P∈→?βα，所有βα→均有：wBAwA→→或成立，其中,,,+∈∈TwVBA則稱Ｇ為３型文法，或正則文法，對(duì)應(yīng)的Ｌ（Ｇ）稱３型語言。（9）什么叫左線性文法？什么叫右線性文法？什么叫線性文法文法G={V，T，P，S}，如果對(duì)于P∈→?βα，所有βα→均有：wBxAwA→→或成立，,,,,*TwxVBA∈∈則稱Ｇ為線性文法。?文法G={V，T，P，S}，如果對(duì)于P∈→?βα，所有βα→均有：wBAwA→→或成立，其中,,,+∈∈TwVBA則稱Ｇ為右線性文法。?文法G={V，T，P，S}，如果對(duì)于P∈→?βα，所有βα→均有：BwAwA→→或成立，其中,,,+∈∈TwVBA則稱Ｇ為左線性文法。（10）既然已經(jīng)定義2-10中允許RL包含空語句ε，那么定理2-6和定理2-7還有什么意義？此為定義與定理的區(qū)別，定義2-10是針對(duì)文法Ｇ是ＲＧ的情況下，定義其產(chǎn)生式加上εS后仍為ＲＧ，Ｇ的語言仍為ＲＬ，而定理2-6和定理2-7針對(duì)的前提條件是如→果Ｌ為ＲＬ，他們都是通過定義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|0S2：S→0|0S|SS3：S→0|0S|ASAS→SAAS→0A0A→S00AS→004：S→0|0S|ASAS→SA|ABBABB→ASAB→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→bbCB→BCbC→bccC→cc解：推導(dǎo)一：S→aBC|aSBCaB→abS=>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)生式集如下,請(qǐng)給出G的每個(gè)語法范疇代表的集合.S→aSa|aaSaa|aAaA→bA|bbbA|bBB→cB|cCC→ccC|DDD→dD|d解:set(D)=a0ck4ue+set(C)={c2ndm|m≥2n≥0}set(B)={cndm|m≥2n≥1}set(A)={bpcndm|p≥1,m≥2,n≥1}set(S)={aqbpcndmaq|p≥1,m≥2,n≥1,q≥1}*******************************************************************************7．給定如下文法，請(qǐng)用自然語言描述它們定義的語言。（吳賢珺02282047）⑴A→aaA│aaBB→Bcc│D#ccD→bbbD│#解：該語言由四部分組成：第一部分是偶數(shù)個(gè)a（至少有兩個(gè)），第二部分是3的倍數(shù)個(gè)b（可以是0個(gè)），第三部分是兩個(gè)“#”號(hào)，第四部分是偶數(shù)個(gè)c（至少有兩個(gè)）。⑵A→0B│1B│2BB→0C│1C│2CC→0D│1D│2D│0│1│2D→0B│1B│2B解：該語言的句子是字母表∑＝{0,1,2}上所有長度為3的倍數(shù)的字符串，且非空。⑶A→0B│1B│2BB→0C│1B│2BC→0E│1D│2D│0│1│2D→0C│1B│2BE→0E│1D│2D│0│1│2解：觀察發(fā)現(xiàn)C和E所對(duì)應(yīng)產(chǎn)生式右部是相同的。所以將文法化簡成如下的形式：A→0B│1B│2BB→0C│1B│2BC→0C│1D│2D│0│1│2D→0C│1B│2B作出狀態(tài)圖如下：D可以看出從初始狀態(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│bAA→a│aS│BAAB→b│bS│ABB解：由于該文法所確定的語言一時(shí)不易看出，可以先考慮簡單的形式：S→aB│bAA→a│aSB→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│bAA→a│aS│CAB→b│bS│DBC→BAD→AB發(fā)現(xiàn)插入的C和D所導(dǎo)入的A和B是成對(duì)的，原文法所確定的語言可能就是字母表∑＝{a,b}上所有含有相同個(gè)a和b的字符串，且非空。從上面簡單形式的文法中已經(jīng)看到，它所確定的字符串比a和b個(gè)數(shù)相同的所有串少的只是多個(gè)a或b連