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

第一章參考答案1.1請用列舉法給出下列集合。 （吳賢珺 02282047） 你知道的各種顏色。解：紅，橙，黃，綠，青，藍(lán)，紫 大學(xué)教師中的各種職稱。解：助教，講師，副教授，教授 你所學(xué)過的課程。解：語文，數(shù)學(xué)，英語，物理，化學(xué)，生物，歷史，地理，政治 你的家庭成員。解：父親，母親，妹妹，我 你知道的所有交通工具。解：汽車，火車，飛機(jī)，輪船，馬車 字母表a , b上長度小于4的串的集合。解：a,b,aa,bb,ab,ba,aaa,aab,aba,abb,baa,bab,bba,bbb 集合1,2,3,4的冪集。解：,1,2,3,4,1,2,1,3,1,4,2,3,2,4,3,4,1,2,3,1,2,4,1,3,4,2,3,4,1,2,3,4 所有的非負(fù)奇數(shù)。解：1,3,5,7, 0100的所有正整數(shù)。解：1,2,3,100(10) 110之間的和為10的整數(shù)集合的集合。解：設(shè)所求的集合為A，集合A中的元素為Ai（i=1,2,3,），Ai也是集合，Ai中的元素在110之間，并且和為10。根據(jù)集合元素的彼此可區(qū)分性，可以計(jì)算出Ai中元素的最多個(gè)數(shù)，方法是：把1開始的正整數(shù)逐個(gè)相加，直到等于10（即10=1+2+3+4），這樣，Ai中最多有4個(gè)元素。原因是：從最小的1開始，每次加入新的元素都只依次增加1，這樣相加的和最小，要加到10，元素個(gè)數(shù)就最多。求出最大的Ai4后，再求出元素個(gè)數(shù)為3，2，1的集合就可以了。 故A=10,1,9,2,8,3,7,4,6,1,2,7,1,3,6,1,4,5,2,3,5,1,2,3,41.2 請用命題法給出下列集合 1.3 給出下列集合的冪集.（02282075 馮蕊）(1) (2) (3) ,(4) ,0,00(5) 0,1解答: (1) (2) ,(3) ,(4) ,0,00,0,00,0,00,0,00(5) ,0,1,0,11.4.列出集合0，1，2，3，4中 (褚穎娜 02282072)（1） 所有基數(shù)為3的子集0，1，2，0，1，3，0，1，4，0，2，3，0，2，4，.1，2，3，1，2，4，1，3，4，0，3，4，2，3，4（2） 所有基數(shù)不大于3的子集，0，1，2，3，4，3，4，2，4，2，3，1，4，1，3，0，4，0，3，0，2，1，2，0，1，0，1，2，0，1，30，1，4，0，2，3，0，2，4，.1，2，3，1，2，4，1，3，4，0，3，4，2，3，41.5解答： 1、3、8、10、11、12、16正確1.6證明下列各題目 （02282081 劉秋雯）1）A=B，iff A是B的子集且B是A的子集證明：充分條件： A=B則由集合相等的定義知對于任何xA，有xBA為B的子集同理，B為A的子集必要條件：A為B的子集 對于任何xA，都有xB又B為A的子集，對于任何xB有，xA由集合相等的定義知，A=B2）如果A為B的子集，則|A|=|B|證明：A為B的子集，則對于任何xA有xB,存在一個(gè)集合C 使B=AC 且AC為空集則|B|=|A|+|C|C|=0|A|=|B|3）如果A為B的真子集，則|A|=|B|證明：（1）當(dāng)A為有窮集合時(shí)，因?yàn)锳為B的真子集，且則對于任何xA有xB,且存在B的x，此x不A存在一個(gè)非空集合C ， 使B=AC 且AC為空集則|B|=|A|+|C| 且|C|=1|A|B|（2）當(dāng)A為無窮集合，因?yàn)锳為B的真子集，則B一定也為無窮集合，|A|，|B|A|=|B|綜合（1），（2）所述，|A|0,都有z*,均有xzL與yzL同時(shí)成立或者同時(shí)不成立(只有當(dāng)z1n|n0的時(shí)候,才同時(shí)成立,否則不成立)(2) x,y0n1m|n0,m=0,都有z*,均有xzL與yzL同時(shí)成立或者同時(shí)不成立(只有當(dāng)z0n1m|n,m0的時(shí)候,才同時(shí)成立,否則不成立)(3) x,y0n1m|n,m0,都有z*,均有xzL與yzL同時(shí)成立或者同時(shí)不成立(無論z取何值,都不同時(shí)成立)三個(gè)等價(jià)類為0n1m|n0,m00n1m|n0,m=0和除此之外的0,1*上的字符1.18 RL確定的0，1*的等價(jià)分類為： 10=x10y|x,y0,1*1n|n1 0=0m1n|m-n=0=0n1n|n0 1=0m1n|m-n=12=0m1n|m-n=2.h=0m1n|m-n=h.其中，n，m均為非負(fù)整數(shù)。1.19.給出下列對象的遞歸定義 (02282072 褚穎娜)1 n個(gè)二元關(guān)系的合成(1) R1R2=(a,c)|$(a,b) R1且$(b,c) R2(2) R1R2Rn = (d,g)|$(d,e)R1R2 Rn-1且$(f,g) Rn 2 無向圖中路的長度在無向圖中，若兩頂點(diǎn)v1,v2之間存在一條無向邊，則v1,v2是的一條長位的路若v1,v2vn-1為一條長度為k-1的路，且vn-1,vn存在一條無向邊，則v1，v2vn-1,vn為的一條長度為k的路3 有向圖中路的長度在有向圖中，若兩頂點(diǎn)v1,v2之間存在一條有向邊，則v1,v2是的一條長位的路若v1,v2vn-1為一條長度為k-1的路，且vn-1,vn存在一條有向邊，則v1，v2vn-1,vn為的一條長度為k的路4 n個(gè)集合的乘積S1S2=(a,b)|a S1且b S2S1 S2Sn=(d,e)|d S1 S2Sn-1且e Sn 5 字母a的n次冪(1) a0=1;(2) an=an-1a;6 字符串x的倒序若x為單字符，則x的倒序是它本身若x的倒序?yàn)閥, 若x后跟一字符a, 則xa的倒序?yàn)閍y;7 字符串x的長度若x為空串e，則|x|=0;若字符串x的長度為k,其xa或ax的長度為k+18 自然數(shù)0為自然數(shù)，如果x為自然數(shù)，則x+1為自然數(shù)1.20.使用歸納法證明下列各題。 (吳玉涵 02282091)121下列集合中哪些是字母表。 (1 ) 1,2。 (2 ) a,b,c,z。 (3 ) 。 (4) a,b,a,c。 (5) 0，1，2，3，,n,。 (6) a,d,fa,b,c,z。 解答：字母表為 (1) (2) (6) (3)不滿足字母表的非空性，(4)不滿足字母表的可區(qū)分性，(5)是無窮集合不滿足字母表的有窮性。22設(shè)a, b，求字符串a(chǎn)aaaabbbba的所有前綴的集合，后綴的集合，真前綴的集合，真后綴的集合。 （吳賢珺 02282047） 解： 前綴：,a,aa,aaa,aaaa,aaaaa,aaaaab,aaaaabb,aaaaabbb,aaaaabbbb,aaaaabbbba 后綴: ,a,ba,bba,bbba,bbbba,abbbba,aabbbba,aaabbbba,aaaabbbba,aaaaabbbba 真前綴: ,a,aa,aaa,aaaa,aaaaa,aaaaab,aaaaabb,aaaaabbb,aaaaabbbb 真后綴: ,a,ba,bba,bbba,bbbba,abbbba,aabbbba,aaabbbba,aaaabbbba 23=aa,ab,bb,ba，求字符串a(chǎn)aaaabbbba的所有前綴的集合、后綴的集合、真前綴的集合、真后綴的集合。 （02282015 郭會）解：由前綴、后綴、真前綴、真后綴的集合可以有：其前綴集合為：,aa,aaaa,aaaaab,aaaaabbb,aaaaabbbba其真前綴集合為：,aa,aaaa,aaaaab,aaaaabbb其后綴集合為：,ba,bbba,abbbba, aaabbbba, aaaaabbbba 其真后綴集合為：,ba,bbba,abbbba, aaabbbba1.25抽象技術(shù)為什么對計(jì)算機(jī)技術(shù)特別重要？ （段季芬）對于計(jì)算機(jī)技術(shù)方面的人來說，計(jì)算思維能力是必需的，這是學(xué)科本身決定的。計(jì)算機(jī)科學(xué)與技術(shù)學(xué)科所要解決的根本問題是什么能被有效的自動化。現(xiàn)代計(jì)算機(jī)技術(shù)認(rèn)為，要想有效的實(shí)現(xiàn)自動化，必須經(jīng)過抽象進(jìn)行形式化。126 為什么要求字母表示非空有窮集？ （唐明珠 02282084）解答：字母表是非空有窮集合，由字母表中的元素連接而成的字符串叫做字母表上的句子。假設(shè)字母表為空集，則字母表中唯一的元素就是不論如何組合，其組成的句子都為空，其研究就失去了意義，所以字母表要具有非空性。1.27. 考慮一下,為什么要研究句子的前綴,后綴?解: 形式語言是研究自然語言和人工語言的數(shù)學(xué)工具，只研究組成規(guī)則，不研究語義。而我們將語言看做句子的集合,句子看做字母按照一定規(guī)則組成的字符串,故主要根據(jù)規(guī)則的形式區(qū)分語言類,大部分問題都可轉(zhuǎn)化為判定某個(gè)句子是否屬于某個(gè)語言的問題.而這就要求從一個(gè)句子的結(jié)構(gòu)出發(fā),而一個(gè)整體的句子在結(jié)構(gòu)上將其劃成幾個(gè)部分,對于我們的研究會有很大的幫助.事實(shí)上研究句子的前綴,后綴,也就是為了將句子結(jié)構(gòu)進(jìn)行有意識的劃分而更加方便的研究句子,看其是否符合某個(gè)形式語言的組成規(guī)則.28令1, 0，下列語言在結(jié)構(gòu)上有什么樣的特點(diǎn)？（吳賢珺 02282047）0n1nn1。解：該語言的每一個(gè)句子由二部分構(gòu)成，這二部分的組成依次為：0、1。其中，每部分的0或1的個(gè)數(shù)相等，且都不小于1個(gè)。0n1mn, m1。解：該語言的每一個(gè)句子由二部分構(gòu)成，這二部分的組成依次為：0、1。其中，每部分的0或1的個(gè)數(shù)不一定相等，但都不小于1個(gè)。0n1n0nn1。解：該語言的每一個(gè)句子由三部分構(gòu)成，這三部分的組成依次為：0、1、0。其中，每部分的0或1的個(gè)數(shù)相等，且都不小于1個(gè)。0n1m0kn, m, k1。解：該語言的每一個(gè)句子由三部分構(gòu)成，這三部分的組成依次為：0、1、0。其中，每部分的0或1的個(gè)數(shù)不一定相等，但都不小于1個(gè)。0n1n0nn0。解：該語言的每一個(gè)句子由三部分構(gòu)成，這三部分的組成依次為：0、1、0。其中，每部分的0或1的個(gè)數(shù)相等，并且可以都為0。xxTx, 。解：該語言的每一個(gè)句子從前向后看和從后向前看時(shí)，有一部分是對稱相等的。而且，這對稱相等的兩個(gè)串中間一定有另外一個(gè)串。x xTx, 。解：該語言的特點(diǎn)是在其句子中一定可以找到這樣的一個(gè)串：該串是從句子的第一個(gè)字符開始的連續(xù)的串，且緊跟該串之后的連續(xù)一段字符串恰好是該串從后往前看是的那個(gè)串，而且這樣的兩個(gè)串之后一定還有另外一個(gè)字符串。aaa,。解：該語言的每一個(gè)句子有這樣的特點(diǎn)：該句子的第一個(gè)字符和最后一個(gè)字符都是0或都是1，且該句子的長度不小于3。 ,0,1,11,01,10,11,000,。解：該語言的句子是所有由0和1構(gòu)成的串，包括空串。0,1,00,01,10,11,000,。解：該語言的句子是所有由0和1構(gòu)成的串，不包括空串。1.29設(shè)L1，L2，L3，L4分別是1,2,3,4上的語言，能否說L1，L2，L3，L4都是某個(gè)字母表上的語言？如果能，請問這個(gè)字母表是怎么樣的？（劉鈺 02282083）答：能 =12341.30 設(shè)分別是上的語言，證明下面的等式成立。（1）設(shè)故原式得證（2）設(shè)故，原式得證（3）如果如果，假設(shè)則，而故，原式得證（4）如果如果，假設(shè)則，而故，原式得證（5）=故，原式得證（6）故，原式得證（7）故，原式得證（8）設(shè)則，因此，當(dāng)k=1,2,n又因?yàn)楣室虼送砜勺C綜上故，原式得證（9）當(dāng)時(shí)，原式顯然成立當(dāng)時(shí)，設(shè)因?yàn)樗怨剩降米C（10）因?yàn)?，所以，故，原式得證（11）設(shè)則，因此，當(dāng)k=1,2,n又因?yàn)楣室虼送砜勺C綜上故，原式得證（12）由8小題結(jié)論可以推得故，原式得證1.31設(shè)L1，L2，L3，L4分別是1，2，3，4上的語言，證明下列等式成立否 (段季芬)（1）（L1L2）*=（L2L1）*不成立 例如： L1=a，L2=b，則（L1L2）*=（ab）*=，ab,abab,ababab,. 而（L2L1）*=（ba）*=,ba.baba,bababa,. 顯然不等。（2）L1+=L1+L1+不成立 例如： L1=0，那么L1+=L1UL12UL13U。=0，00，000，。而L1+L1+=00，000，0000，。，比L1+少基本項(xiàng)L1 可得知L1+L1+是L1+的子集 （3）L1*=L1*L1*正確因?yàn)長1*L1*=（L10UL1UL12UL13U。）（L10UL1UL12UL13U。） =（L10UL1UL12UL13U。）L10U（L10UL1UL12UL13U。）L1U。 =（L10UL1UL12UL13U。）UAUBU。 從觀察可知A是（L10UL1UL12UL13U。）的真子集，B 是A的真子集，推知后面一項(xiàng)是前面的一項(xiàng)的真子集，根據(jù)吸收規(guī)則所以原式=L10UL1UL12UL13U。=L1*（1） （L1UL2）*=L2*UL1*不正確 例如： L1=a，L2=b，左邊=a,b*=,a,b,aa,ab,bb,右邊=，b,bb,bbb,U,a,aa,aaa,.=,a,b,aa,bb,aaa,bbb, 沒有a*b*項(xiàng) 肯定不等（2） （L1L2UL1）*L1=L1（L2L1UL1）*正確（3） L2（L1L2UL2）*L1=L1L1*L2（L1L1*L2）*不正確假設(shè)L1=a，L2=b，L2（L1L2UL2）*L1表示的語言肯定以b打頭，而L1L1*L2（L1L1*L2）*表示的語言肯定以a開頭（4） （L1+）*=（L1*）+=L1*正確（L1+）*=（L1UL12UL13U。）*=，（L1UL12UL13U。），（L1UL12UL13U。）2，（L1UL12UL13U。）3。 由于（L1UL12UL13U。）n是（L1UL12UL13U。）n-1的子集（L1+）*表示的語言就是 ，（L1UL12UL13U。）表示的語言即L1*，所以（L1+）*=L1*（L1*）+=（L10L1UL12UL13U。）+=（L10L1UL12UL13U。），（L10L1UL12UL13U。）2，（L10L1UL12UL13U。）3，。由于（L10UL1UL12UL13U。）n是（L10UL1UL12UL13U。）n-1的子集（L1*）+表示的語言就是（L10UL1UL12UL13U。）表示的語言即L1*，所以（L