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

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

第一章參考答案 1.1請(qǐng)用列舉法給出下列集合。 （吳賢珺 02282047） ⑴ 你知道的各種顏色。 解：{紅，橙，黃，綠，青，藍(lán)，紫} ⑵ 大學(xué)教師中的各種職稱。 解：{助教，講師，副教授，教授} ⑶ 你所學(xué)過的課程。 解：{語文，數(shù)學(xué)，英語，物理，化學(xué)，生物，歷史，地理，政治} ⑷ 你的家庭成員。 解：{父親，母親，妹妹，我} ⑸ 你知道的所有交通工具。 解：{汽車，火車，飛機(jī)，輪船，馬車} ⑹ 字母表{a , b}上長(zhǎng)度小于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,…} ⑼ 0～100的所有正整數(shù)。 解：{1,2,3,…,100} (10) 1～10之間的和為10的整數(shù)集合的集合。 解：設(shè)所求的集合為A，集合A中的元素為Ai（i=1,2,3,…），Ai也是集合，Ai中的元素在1～10之間，并且和為10。根據(jù)集合元素的彼此可區(qū)分性，可以計(jì)算出Ai中元素的最多個(gè)數(shù)，方法是：把1開始的正整數(shù)逐個(gè)相加，直到等于10（即10=1+2+3+4），這樣，Ai中最多有4個(gè)元素。原因是：從最小的1開始，每次加入新的元素都只依次增加1，這樣相加的和最小，要加到10，元素個(gè)數(shù)就最多。 求出最大的∣Ai∣＝4后，再求出元素個(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,4}} 1.2 請(qǐng)用命題法給出下列集合 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,1}} 1.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，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} 1.5解答： 1、3、8、10、11、12、16正確 1.6證明下列各題目 （02282081 劉秋雯） 1）A=B，iff A是B的子集且B是A的子集 證明： 充分條件： ∵A=B 則由集合相等的定義知 對(duì)于任何x∈A，有x∈B ∴A為B的子集 同理，B為A的子集 必要條件： ∵A為B的子集 ∴ 對(duì)于任何x∈A，都有x∈B 又∵B為A的子集， ∴對(duì)于任何x∈B有，x∈A 由集合相等的定義知，A=B 2）如果A為B的子集，則|A|〈=|B| 證明： A為B的子集，則對(duì)于任何x∈A 有x∈B, ∴存在一個(gè)集合C 使B=A∪C 且A∩C為空集 則|B|=|A|+|C| |C|〉=0 ∴|A|〈=|B| 3）如果A為B的真子集，則|A|〈=|B| 證明： （1）當(dāng)A為有窮集合時(shí)，因?yàn)锳為B的真子集，且則對(duì)于任何x∈A 有x∈B, 且存在∈B的x，此x不∈A ∴存在一個(gè)非空集合C ， 使B=A∪C 且A∩C為空集 則|B|=|A|+|C| 且|C|〉=1 ∴|A|〈|B| （2）當(dāng)A為無窮集合，因?yàn)锳為B的真子集，則B一定也為無窮集合，|A|＝∞，|B|＝∞ ∴|A|=|B| 綜合（1），（2）所述，|A|<=|B| 4）如果A是有窮集且A為B的真子集則|A|〈|B| 證明： 見上題證明（1） 5）如果A為B的子集，則對(duì)于任何x∈A，有x∈B 證明： 若A為B的子集，則由子集定義可知，對(duì)于任何x∈A，有x∈B 6）如果A是B的真子集，則對(duì)于任何x∈A，有x∈B，并且存在x∈B，但x不∈A 證明： 由真子集的定義可證 7）如果A為B的子集，B為C的子集，則A為C的子集 證明： A為B的子集，B為C的子集 則對(duì)于任何x∈A，則x都∈B， 且，又對(duì)于任何y∈B，則y∈C，∴對(duì)于任何x∈A，x∈C ∴A為C的子集 8）如果A為B的真子集，B為C的真子集，則A為C的真子集 證明： A為B的真子集，B為C的真子集 則對(duì)于任何x∈A，則x都∈B， 且，存在x∈B但次x不∈A， 又對(duì)于任何y∈B，則y∈C，存在y∈C但此y不∈B， ∴對(duì)于任何x∈A，x∈C，存在x∈C.x不∈A ∴A為C的真子集 9）如果A為B的子集，B為C的真子集，則A為C的真子集 證明： 因?yàn)锳為B的子集，B為C的真子集 則對(duì)于任何x∈A， x都∈B，且x都∈C 又對(duì)于任何y∈B，則y∈C，存在y∈C但此y不∈B，則y不∈A ∴對(duì)于任何x∈A，x∈C，存在x∈C.x不∈A ∴A為C的真子集 10）如果A為B的真子集，B為C的子集，則A為C的真子集 證明： A為B的真子集，B為C的子集 則對(duì)于任何x∈A，則x都∈B， 且存在x∈B但次x不∈A， 又對(duì)于任何y∈B，則y∈C ∴對(duì)于任何x∈A，x∈C，存在x∈C.x不∈A ∴A為C的真子集 11）如果A=B，則|A|=|B| 證明： A=B，則A與B所含元素相同 ∴|A|=|B| 12）如果A為B的子集，B為C的真子集，或如果A為B的真子集，B為C的子集，則A為C的真子集 證明：證明見9，10 1.7 A = {1,2,3,4,5,6} B = {1,3,5} C = {2,4,6} U = {0,1,2,3,4,5,6,7,8,9} (1). = {1,3,5} = B (2). = {1,3,5} ={1,2,3,4,5,6} = A (3). = {1,3,5} ={0,1,3,5,7,8,9} = (4).A-B-C = {2,4,6} – {2,4,6} = (5).A B C = A = (6). = {1,3,5}{0,7,8,9}{0,7,8,9} = {0,1,3,5,7,8,9} = (7). = = = (8). = = = ={1，2，3，4，5，6} 1．8 對(duì)論域U上的集合A、B、C，證明以下結(jié)論成立。 （02282047 吳賢珺） ⑴ A∪B＝B∪A 證：對(duì)任意的x， x∈A∪B x∈Ax∈B x∈Bx∈A x∈B∪A 故A∪BB∪A 且 B∪AA∪B 則 A∪B＝B∪A。 ⑵ (A∪B)∪C＝A∪(B∪C) 證：對(duì)任意的x， x∈(A∪B)∪C x∈(A∪B)x∈C (x∈Ax∈B)x∈C x∈Ax∈Bx∈C x∈A(x∈Bx∈C) x∈Ax∈(B∪C ) x∈A∪(B∪C) 故(A∪B)∪C A∪(B∪C) 且 A∪(B∪C) (A∪B)∪C 則 (A∪B)∪C＝A∪(B∪C)。 ⑶ A∪B＝A iff BA 證： ① 由BA∪B及 A∪B＝A知 BA。 ② 由BA 知x∈B, x∈A 則對(duì)任意的x， x∈A∪B x∈Ax∈B x∈A 故 A∪BA，又AA∪B，所以 A∪B＝A。 綜合①②得到 A∪B＝A iff BA。 ⑷ A(B∪C)＝(AB)∪(A∪C) 證：對(duì)任意的有序?qū)?a, b)， (a, b)∈A(B∪C) a∈Ab∈(B∪C) a∈A(b∈Bb∈C) (a∈Ab∈B)( a∈Ab∈C) (a, b)∈AB(a, b)∈AC (a, b)∈(AB)∪(AC) 故A(B∪C) (AB)∪(A∪C) 且 (AB)∪(A∪C) A(B∪C) 則 A(B∪C)＝(AB)∪(A∪C)。 ⑸ (B∩C)A＝(BA)∩(CA) 證：對(duì)任意的有序?qū)?b, a)， (b, a)∈(B∩C)A b∈(B∩C)a∈A (b∈Bb∈C)a∈A (b∈Ba∈A)(b∈Ca∈A) (b, a)∈BA(b, a)∈CA (b, a)∈(BA)∩(CA) 故(B∩C)A (BA)∩(CA) 且 (BA)∩(CA) (B∩C)A 則 (B∩C)A＝(BA)∩(CA)。 ⑹ A(B－C)＝(AB)－(AC) 證：對(duì)任意的有序?qū)?a, b)， (a, b)∈A(B－C) a∈Ab∈(B－C) a∈A(b∈BbC) (a∈Ab∈B)( a∈AbC) (a, b)∈AB(a, b)AC (a, b)∈(AB)－(AC) 故A(B∪C) (AB)∪(A∪C) 且 (AB)∪(A∪C) A(B∪C) 則 A(B∪C)＝(AB)∪(A∪C)。 需要說明的是：對(duì)于 (a, b)∈AB(a, b)AC (a∈Ab∈B)( a∈AbC 本來，由(a, b)AC 只能得到 (aAbC)。但是(a, b)∈AB，故a∈A， 這樣，必須bC。 ⑺ 如果 AB，則2A2B 證：對(duì)任意的C，C∈2A CA 由于AB，故CB，則C∈2B，從而2A2B。 ⑻ 2＝2A∩2B 證：對(duì)任意的C， C∈2 CA∩B CACB C∈2AC∈2B C∈2A∩2B 則 2 2A∩2B 且 2A∩2B 2，故2＝2A∩2B。 ⑼ │A∪B│≤│A│＋│B│ 證：由容斥原理，│A∪B│＝│A│＋│B│－│A∩B│ ① 當(dāng)A∩B≠Φ時(shí)，│A∪B│＜│A│＋│B│ ② 當(dāng)A∩B＝Φ時(shí)，│A∪B│＝│A│＋│B│ 由①②知│A∪B│≤│A│＋│B│。 (10) (B－C)A＝(BA)－(CA) 證：對(duì)任意的有序?qū)?b, a)， (b, a)∈(B－C)A b∈(B－C)a∈A (b∈BbC)a∈A (b∈Ba∈A)(bCa∈A) (b, a)∈BA(b, a)CA (b, a)∈(BA)－(CA) 故 (B－C)A (BA)－(CA) 且 (BA)－(CA) (B－C)A 則 (B－C)A＝(BA)－(CA)。 需要說明的是：對(duì)于 (b, a)∈BA(b, a)CA (b∈Ba∈A)(bCa∈A) 本來，由(b, a)CA 只能得到 (aAbC)。但是(b, a)∈BA，故a∈A， 這樣，必須bC。 (11) 如果AB，則 證：對(duì)任意的x，x∈xB 由于AB，故xA，即x∈。因此，。 (12) B＝A∪B＝U且A∩B＝Φ 證：① 由B＝ 以及的定義知，A∪B＝A∪＝U，A∩B＝A∩＝Φ。 ② 由A∩B＝Φ知，對(duì)任意的x∈B，xA，即x∈B，x∈，故B。 又由A∪B＝U知，對(duì)任意的x∈，xA ，則x∈B，故B。 這樣，B＝。 綜合①②得，B＝A∪B＝U且A∩B＝Φ。 (13) ＝∪ 證：對(duì)任意的x， x∈ x(A∩B) xAxB x∈x∈ x∈(∪) 則∪ 且 ∪ 故＝∪。 (14) ＝∩ 證：對(duì)任意的x， x∈ x(A∪B) xAxB x∈x∈ x∈(∩) 則∩ 且 ∩ 故＝∩。 1.9解答 (6) R={(a,a),(b,b),(c,c),(d,d),(e,e),(a,b),(b,c),(a,c)} (9) R={(a,a),(b,b),(c,c),(d,d),(e,e), (a,b),(b,c),(a,c),(b,a),(c,b),(c,a)} 1.10 設(shè)R1和R2是集合{a,b,c,d,e}上的二元關(guān)系,其中, R1={(a,b),(c,d),(b,d),(b,b),(d,e)}, R2={(a,a),(b,c),(d,c),(e,d),(c,a)} 求:R1R2,R2R1,R1+,R2+,R1*,R2*. 解答: R1R2={(a,c),(c,c),(b,c),(d,d)} R2R1={(a,b),(b,d),(d,d),(e,e),(c,b)} R1+= {(a,b),(c,d),(b,d)(b,b),(d,e),(a,d),(a,e),(b.e),(c,e)} R2+={(a,a),(b,c),(d,c),(e,d),(c,a)(b,a),(d,a),(e,c),(e,a)} R1*= R1+{(a,a),(b,b),(c,c),(d,d),(e,e)} R2*= R2+{(a,a),(b,b),(c,c),(d,d),(e,e)} 1.11.設(shè)R={(a,b),(c,d),(b,d)}是集合{a,b,c,d,e}上的二元關(guān)系,求: （敖 雪 峰） (1) R的傳遞閉包. (2) R的自反傳遞閉包. 解: (1) R的傳遞閉包是{(a,b),(c,d),(b,d),(a,d)}. (2) R的自反傳遞閉包是{(e,e),(a,a),(b,b),(c,c),(d,d),(a,b),(c,d),(b,d),(a,d)}. 1．12 設(shè)和是集合{a,b,c,d,e}上的二元關(guān)系，請(qǐng)證明下列關(guān)系。 (唐明珠 02282084) (1) 。 證明：用反證法，假設(shè)。 設(shè)。 則 這與相矛盾， 所以。 (2) 。 證明：任取(x.,y),其中x,y，使得 所以得證。 (3) 。 證明：任取(x.,y),其中x,y，使得。 所以得證 (4 ) 。 證明：任取(x.,y),其中x,y，使得。 所以得證。 (5) 。 證明：任取(x.,y),其中x,y，使得。 所以得證。 (6) 。 證明：任取(x.,y),其中x,y，使得。 所以得證。 1.13 通常意義下的=是自然數(shù)集上的一個(gè)等價(jià)關(guān)系，請(qǐng)按照該等價(jià)關(guān)系給出自然數(shù)集的等價(jià)類 （02282075 馮蕊） “=”關(guān)系將自然數(shù)集N分成無窮多個(gè)等價(jià)類：{0}，{1}，{2}，{3}，{4}，{5}，{6}，…… 1.14.在什么樣的假設(shè)下，人與人之間的“同鄉(xiāng)關(guān)系”是等價(jià)關(guān)系。當(dāng)“同鄉(xiāng)關(guān)系”在給定的限定下成為等價(jià)關(guān)系時(shí)，它將所有的中國(guó)人分成什么樣的等價(jià)類？ (吳玉涵 02282091) 答：假設(shè)出生在同一個(gè)省的關(guān)系為同鄉(xiāng)關(guān)系。按照這樣的同鄉(xiāng)關(guān)系將中國(guó)人按照出生省份的不同劃分出等價(jià)類。 1.16 上的二元關(guān)系RL 定義為：對(duì)任給的x,y，如果對(duì)于，均有xz與yzL，同時(shí)成立或者同時(shí)不成立，則xRLy。 (周期律 02282067) 證明： （1）對(duì)于 xz與xzL顯然是同時(shí)成立或同時(shí)不成立，對(duì)于，故xRLx，RL 具有自反性。 對(duì)于，如果xRLy, 故xz與yzL同時(shí)成立或同時(shí)不成立，顯然故yz與xzL同時(shí)成立或同時(shí)不成立，故yRLx, RL 具有對(duì)稱性。 對(duì)于,如果xRLy, yRLp, 故xz與yzL同時(shí)成立或同時(shí)不成立，并且故yz與pzL同時(shí)成立或同時(shí)不成立，故xz與pz同時(shí)成立或同時(shí)不成立，故xRLp，故RL具有傳遞性。 綜上，關(guān)系RL是在上的等價(jià)關(guān)系。 （2）如果對(duì)于任給的x,y，如果xRLy， 故對(duì)于，xz與yzL同時(shí)成立或同時(shí)不成立， 對(duì)于,如果xzp,因?yàn)閦p,又因?yàn)閤RLy, 故yzpL， 同理，可以證明如果xzp,因?yàn)閦p,又因?yàn)閤RLy, 故yzpL， 因此，對(duì)于，xzp與yzpL同時(shí)成立或同時(shí)不成立， 故如果對(duì)于任給的x,y，如果xRLy，則必有xzRLyz。 綜上，該關(guān)系的等價(jià)性和右不變性均得以證明。 1.17 設(shè){0,1}*上的語言L={0n1m|n,m≥0},請(qǐng)給出{0,1}*關(guān)于L所確定的等價(jià)關(guān)系RL的等價(jià)類. 設(shè)L是Σ上的一個(gè)語言,Σ*上的二元關(guān)系RL定義為:對(duì)任給的x,yΣ*,如果對(duì)于"zΣ*,均有xzL與yzL同時(shí)成立或者同時(shí)不成立,則xRLy. 根據(jù)上述定義可知, {0,1}*關(guān)于L所確定的等價(jià)關(guān)系RL的等價(jià)類有三個(gè). (1) "x,y{0n1m|n≥0,m>0},都有"zΣ*,均有xzL與yzL同時(shí)成立或者同時(shí)不成立 (只有當(dāng)z{1n|n≥0}的時(shí)候,才同時(shí)成立,否則不成立) (2) "x,y{0n1m|n≥0,m=0},都有"zΣ*,均有xzL與yzL同時(shí)成立或者同時(shí)不成立 (只有當(dāng)z{0n1m|n,m≥0}的時(shí)候,才同時(shí)成立,否則不成立) (3) "x,y{0n1m|n,m≥0},都有"zΣ*,均有xzL與yzL同時(shí)成立或者同時(shí)不成立 (無論z取何值,都不同時(shí)成立) 三個(gè)等價(jià)類為{0n1m|n≥0,m>0}{0n1m|n≥0,m=0}和除此之外的{0,1}*上的字符 1.18 RL確定的{0，1}*的等價(jià)分類為： [10]={x10y|x,y∈{0,1}*}∪{1n|n≥1} [0]={0m1n|m-n=0}={0n1n|n≥0} [1]={0m1n|m-n=1} [2]={0m1n|m-n=2} . . . [h]={0m1n|m-n=h} . . . 其中，n，m均為非負(fù)整數(shù)。 1.19.給出下列對(duì)象的遞歸定義 (02282072 褚穎娜) 1． n個(gè)二元關(guān)系的合成 (1) R1R2={(a,c)|$(a,b) R1且$(b,c) R2} (2) R1R2……Rn = {(d,g)|$(d,e)R1R2…… Rn-1且$(f,g) Rn } 2． 無向圖中路的長(zhǎng)度 在無向圖Ｇ中，若兩頂點(diǎn)v1,v2之間存在一條無向邊，則v1,v2是Ｇ的一條長(zhǎng)位１的路 若v1,v2……vn-1為一條長(zhǎng)度為k-1的路，且vn-1,vn存在一條無向邊，則v1，v2……vn-1,vn為Ｇ的一條長(zhǎng)度為k的路 3． 有向圖中路的長(zhǎng)度 在有向圖Ｇ中，若兩頂點(diǎn)v1,v2之間存在一條有向邊，則v1,v2是Ｇ的一條長(zhǎng)位１的路 若v1,v2……vn-1為一條長(zhǎng)度為k-1的路，且vn-1,vn存在一條有向邊，則v1，v2……vn-1,vn為Ｇ的一條長(zhǎng)度為k的路 4． n個(gè)集合的乘積 S1S2={(a,b)|a S1且b S2} S1 S2……Sn={(d,e)|d S1 S2……Sn-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的長(zhǎng)度 若x為空串e，則|x|=0; 若字符串x的長(zhǎng)度為k,其xa或ax的長(zhǎng)度為k+1 8． 自然數(shù) 0為自然數(shù)， 如果x為自然數(shù)，則x+1為自然數(shù) 1.20.使用歸納法證明下列各題。 (吳玉涵 02282091) 1．21下列集合中哪些是字母表。 (1 ) {1,2}。 (2 ) {a,b,c,…,z}。 (3 ) 。 (4) {a,b,a,c}。 (5) {0，1，2，3，…,n,…}。 (6) {a,d,f}{a,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 郭會(huì)） 解： 由前綴、后綴、真前綴、真后綴的集合可以有： 其前綴集合為：{ε,aa,aaaa,aaaaab,aaaaabbb,aaaaabbbba} 其真前綴集合為：{ε,aa,aaaa,aaaaab,aaaaabbb} 其后綴集合為：{ε,ba,bbba,abbbba, aaabbbba, aaaaabbbba } 其真后綴集合為：{ε,ba,bbba,abbbba, aaabbbba} 1.25抽象技術(shù)為什么對(duì)計(jì)算機(jī)技術(shù)特別重要？ （段季芬） 對(duì)于計(jì)算機(jī)技術(shù)方面的人來說，計(jì)算思維能力是必需的，這是學(xué)科本身決定的。計(jì)算機(jī)科學(xué)與技術(shù) 學(xué)科所要解決的根本問題是什么能被有效的自動(dòng)化?，F(xiàn)代計(jì)算機(jī)技術(shù)認(rèn)為，要想有效的實(shí)現(xiàn)自動(dòng)化， 必須經(jīng)過抽象進(jìn)行形式化。 1．26 為什么要求字母表示非空有窮集？ （唐明珠 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è)部分,對(duì)于我們的研究會(huì)有很大的幫助.事實(shí)上研究句子的前綴,后綴,也就是為了將句子結(jié)構(gòu)進(jìn)行有意識(shí)的劃分而更加方便的研究句子,看其是否符合某個(gè)形式語言的組成規(guī)則. 28．令∑＝{1, 0}，下列語言在結(jié)構(gòu)上有什么樣的特點(diǎn)？（吳賢珺 02282047） ⑴＝{0n1n│n≥1}。 解：該語言的每一個(gè)句子由二部分構(gòu)成，這二部分的組成依次為：0、1。其中，每部分的0或1的個(gè)數(shù)相等，且都不小于1個(gè)。 ⑵＝{0n1m│n, m≥1}。 解：該語言的每一個(gè)句子由二部分構(gòu)成，這二部分的組成依次為：0、1。其中，每部分的0或1的個(gè)數(shù)不一定相等，但都不小于1個(gè)。 ⑶＝{0n1n0n│n≥1}。 解：該語言的每一個(gè)句子由三部分構(gòu)成，這三部分的組成依次為：0、1、0。其中，每部分的0或1的個(gè)數(shù)相等，且都不小于1個(gè)。 ⑷＝{0n1m0k│n, m, k≥1}。 解：該語言的每一個(gè)句子由三部分構(gòu)成，這三部分的組成依次為：0、1、0。其中，每部分的0或1的個(gè)數(shù)不一定相等，但都不小于1個(gè)。 ⑸＝{0n1n0n│n≥0}。 解：該語言的每一個(gè)句子由三部分構(gòu)成，這三部分的組成依次為：0、1、0。其中，每部分的0或1的個(gè)數(shù)相等，并且可以都為0。 ⑹＝{xωxT│x, ω∈}。 解：該語言的每一個(gè)句子從前向后看和從后向前看時(shí)，有一部分是對(duì)稱相等的。而且，這對(duì)稱相等的兩個(gè)串中間一定有另外一個(gè)串。 ⑺＝{x xTω│x, ω∈}。 解：該語言的特點(diǎn)是在其句子中一定可以找到這樣的一個(gè)串：該串是從句子的第一個(gè)字符開始的連續(xù)的串，且緊跟該串之后的連續(xù)一段字符串恰好是該串從后往前看是的那個(gè)串，而且這樣的兩個(gè)串之后一定還有另外一個(gè)字符串。 ⑻＝{aωa│a∈,ω∈}。 解：該語言的每一個(gè)句子有這樣的特點(diǎn)：該句子的第一個(gè)字符和最后一個(gè)字符都是0或都是1，且該句子的長(zhǎng)度不小于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è)字母表Σ上的語言？如果能，請(qǐng)問這個(gè)字母表Σ是怎么樣的？ （劉鈺 02282083） 答：能 Σ=Σ1∪Σ2∪Σ3∪Σ4 1.30 設(shè)分別是上的語言，證明下面的等式成立。 （1） 設(shè)故原式得證 （2） 設(shè) 故，原式得證 （3） 如果 如果，假設(shè) 則，而 故，原式得證 （4） 如果 如果，假設(shè) 則，而 故，原式得證 （5） == 故，原式得證 （6） 故，原式得證 （7） 故，原式得證 （8） 設(shè) 則，因此，當(dāng)k=1,2,…n 又因?yàn)? 故因此 同理可證 綜上 故，原式得證 （9） 當(dāng)時(shí)，原式顯然成立 當(dāng)時(shí)，設(shè) 因?yàn)? 所以 故，原式得證 （10） 因?yàn)椋? 所以， 故，原式得證 （11） 設(shè) 則，因此，當(dāng)k=1,2,…n 又因?yàn)? 故因此 同理可證 綜上 故，原式得證 （12） 由8小題結(jié)論可以推得 故，原式得證 1.31設(shè)L1，L2，L3，L4分別是?1，?2，?3，?4上的語言，證明下列等式成立否 (段季芬) （1）（L1L2）*=（L2L1）* 不成立 例如： L1={a}，L2=，則（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)長(zhǎng)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=，左邊={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=，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*，所以（L1*）+=L1* 所以（L1+）*=（L1*）+=L1* （5） L1*L1+=L1+L1*=L1+ 正確 L1*L1+ =（L10UL1UL12UL13U。。。）U（L1UL12UL13U。。。） =（L10UL1UL12UL13U。。。）L1U（L10UL1UL12UL13U。。。）L12U。。。 =（L1UL12UL13U。。。）U（L12UL13UL14。。。）U。。。（后面的項(xiàng)都被第一項(xiàng)吸收） =（L1UL12UL13U。。。）=L1+ 同理可證得L1+L1*=L1+ 1.32 設(shè)，請(qǐng)給出上的下列語言的形式表示。 (1) 所有以0開頭的串。 解答：。 (2) 所有以0開頭，以1結(jié)尾的串。 解答：。 (3) 所有以11開頭，以11結(jié)尾的串。 解答：。 (4) 所有最多有一對(duì)連續(xù)的0或者最多有一對(duì)連續(xù)的1的串。 解答：。 (5) 所有最多有一對(duì)連續(xù)的0并且最多有一對(duì)連續(xù)的1的串。 解答：按照實(shí)際情況分成4類： 1) 只有一對(duì)連續(xù)的0： 。 2) 只有一對(duì)連續(xù)的1：。 3) 沒有連續(xù)的0并且沒有連續(xù)的1：。 4) 有一對(duì)連續(xù)的0和一對(duì)連續(xù)的1： 。 (6) 所有長(zhǎng)度為偶數(shù)的串。 解答： （7）所有長(zhǎng)度為奇數(shù)的串 解答：{0,1},n=1,2 … (8) 所有包含子串01011的串。 解答：。 (9) 所有包含3個(gè)連續(xù)0的子串。 解答：{0,1}*000{0,1}* (10) 所有不包含3個(gè)連續(xù)0的串。 解答：{001，01，1}。 (11) 所有正數(shù)第10個(gè)字符是0的串。 解答：。 (12) 所有倒數(shù)第10個(gè)字符是0的串。 解答：{0,1}0{0,1}。 27