形式语言与自动机理论-蒋宗礼-第一章参考答案.docx

第一章参考答案1.1请用列举法给出以下集合。(吴贤瑞02282047)你知道的各种颜色。解：红，橙，黄，绿，青，蓝，紫大学教师中的各种职称。解：助教，讲师，副教授，教授你所学过的课程。解：语文，数学，英语，物理，化学，生物，历史，地理，政治(4)你的家庭成员。解：父亲，母亲，妹妹，我你知道的所有交通工具。解：汽车，火车，飞机，轮船，马车(6)字母表a,b上长度小于4的串的集合。解：a,b,aa,bb,ab,ba,aaa,aab,aba,abb,baa,bab,bba,bbb)(7)集合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(8)所有的非负奇数。解：1,3,5,7,(9)0100的所有正整数。解：1,2,3,，100(10)110之间的和为10的整数集合的集合。解：设所求的集合为A,集合A中的元素为Ai(i=l,2,3,)，Ai也是集合，Ai中的元素在110之间，并且和为10。根据集合元素的彼此可区分性，可以计算出Ai中元素的最多个数，方法是：把1开始的正整数逐个相加，直到等于10(即IO=I+2+3+4),这样，Ai中最多有4个元素。原因是：从最小的1开始，每次参加新的元素都只依次增加1,这样相加的和最小，要加到10,元素个数就最多。求出最大的IAiI=4后，再求出元素个数为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请用命题法给出以下集合2.(l)x0x100iLxz(2)xx,且IXl<4(3)BB1,2,3,4)(4)LL,M*(5)xx=2n-l,nN(6)(,力I+b=10且4b4,9(7)xx0,l且x的个数是1的个数的两倍(8)xx0,l*,且冲1的个数是10(9)xx0,l且X中倒数第十个字符为1IAIl(10)A.Ax.l,101,A,.=101.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,l,0,l14.列出集合0,L2,3,4中(褚颖娜02282072)(1) 所有基数为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) 所有基数不大于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证明以下各题目1JA=B,iffA是B的子集且B是A的子集证明：充分条件：VA=B那么由集合相等的定义知对于任何x£A,有xB,A为B的子集同理，B为A的子集必要条件：.A为B的子集对于任何x£A,都有xB又TB为A的子集，J对于任何XeB有，xA由集合相等的定义知，A=B2如果A为B的子集，那么IAl<=B证明：A为B的子集，那么对于任何xA有xB,存在一个集合C使B=AUC且AC为空集那么IBl=IA|+|ClC>=O.,.A(=B3如果A为B的真子集，那么IAl<=B证明：(1)当A为有穷集合时，因为A为B的真子集，且那么对于任何xA有xB,且存在B的X,此X不A存在一个非空集合C,使B=AIJC且AC为空集那么IBl=IA+Cl且IeD=1.,.A<B(2)当A为无穷集合，因为A为B的真子集，那么B-定也为无穷集合，A=8,B=IAI=IBI综合(1),(2)所述，IAlV=IBl4如果A是有穷集且A为B的真子集那么IAl<B证明：见上题证明(1)5如果A为B的子集，那么对于任何xA,有xB证明：假设A为B的子集，那么由子集定义可知，对于任何xA,有xB6如果A是B的真子集，那么对于任何xA,有xB,并且存在xB,但X不A证明：由真子集的定义可证7如果A为B的子集，B为C的子集，那么A为C的子集证明：A为B的子集，B为C的子集那么对于任何X七A,那么X都B,且，又对于任何y£B,那么y£C,；对于任何*£人，xC.A为C的子集8如果A为B的真子集，B为C的真子集，那么A为C的真子集证明：A为B的真子集，B为C的真子集那么对于任何X七A,那么X都B,且，存在xB但次X不七A,又对于任何yB,那么yC,存在yC但此y不B,，对于任何x£A,xC,存在x£C.x不EA.A为C的真子集9如果A为B的子集，B为C的真子集，那么A为C的真子集证明：因为A为B的子集，B为C的真子集那么对于任何xA,X都B,且X都C又对于任何y£B,那么yC,存在y£C但此y不B,那么y不A对于任何x0A,xC,存在xC.x不EA,A为C的真子集10如果A为B的真子集，B为C的子集，那么A为C的真子集证明：A为B的真子集，B为C的子集那么对于任何xA,那么X都B,且存在xB但次X不A,又对于任何y£B,那么yC对于任何x6A,xC,存在xC.x不EA.A为C的真子集11如果A=B,那么IAl=IBl证明：A=B,那么A与B所含元素相同.,.A=B12如果A为B的子集，B为C的真子集，或如果A为B的真子集，B为C的子集，那么A为C的真子集证明：证明见明IO1.7A=1,2,3A5,6B=1,3,5C=2,4,6U=0,1,2,3,4,5,6,7,8,9(1) .ApP=1,3,5)=B(2) .(App)IjC=1,3,5J2A6二1,2,3,4,5,6二A(3) .(4PP)U(U-C)=15JO,15,7,8,9)=0,l,3,5,7,8,9二C(4) .A-B-C=2,4,6)-2A6)二(5) .AXBXCX二AX=(6)XB)4JcJa=1,3,5U0,7,8,9U0,7,8,9)=O,1,3,5J,8,9)=C(7) .A×B×AC=A×B×C=A×(a,b)I(aB,bC)或(B,bC)或(B,bC)=(,aC)I(aA,bB,cC)或(,bB,cC)或(A,bB,cC)(8) .4J(AjB)UC=a114Jc=AUC=A=1,2,3,4,5,61. 8对论域U上的集合A、B、C,证明以下结论成立。(02282047吴贤瑜(1) AUB=BUA证：对任意的X,xAUB<z>xAVxB<=>xBvxAOXeBIJA故AUBqBUA且BUAAUB那么AUB=BUAo(2) (AUB)Uc=AU(BUC)证：对任意的X,x(AUB)UC<=>x(AUB)VxC<=>(xAvxB)VxCOXAvxBVxC<z>xAv(xBVxC)<=>xAvx(BUC)<=>xAU(BUC)故(AUB)UCAU(BUC)且AU(BUC)(AUB)UC那么(AUB)UC=AU(BUC)°(3) AUB=AiffBeA证：由BqAUB及AUB=A知BAo由BA知VWB,xA那么对任意的X,xAUBz>xAvxBz>xA故AUBA,又AqAUB,所以AUB=Ao综合得到AUB=AiffBoA0(4) A×(BUC)=(A×B)U(AUC)证：对任意的有序对(a,b),(a,b)A×(BUC)<z>aAb(BUC)<>aA(bBvbC)O(aAbB)v(aAbC)<=>(a,b)A×Bv(a,b)A×C<=>(a,b)(A×B)U(A×C)AX(BUC)(AXB)U(AUC)且(AXB)U(AUC)AX(BUC)那么AX(BUC)=(AXB)U(AUC)o(5) (BnC)XA=(BXA)CI(CXA)证：对任意的有序对(b,a),(b,a)(BC)×A<z>b(BC)aA<z>(bBbC)aA<>(bBaA)(bCaA)<=>(b,a)B×A(b,a)C×A<=>(b,a)(B×A)(C×A)故(BCC)XA(B×A)(C×A)且(BXA)(CXA)(BC)×A那么(BgC)XA=(BXA)G(CXA)O(6) AX(B-C)=(AXB)-(AXC)证：对任意的有序对(a,b),(a,b)A×(B-C)<>aAab(B-C)<>aA(bBb¢C)<z>(aAbB)(aAb¢C)<=>(a,b)A×B(a,b)史AXC<=>(a,b)(AXB)-(AXC)AX(BUC)(AXB)U(AUC)且(AXB)U(AUC)AX(BUC)那么AX(BUC)=(AXB)U(AUC)o需要说明的是：对于(a,b)AXBA(a,b)eAXC本来，由（a,zz>(aAabB)(aAbCb)走AXC只能得到(a¢AvbC)o但是(a,b)£AXB,故aA,这样，必须b足C。(7)如果AqB,那么2A±2B证：对任意的C,C2a=>CqA由于AqB,故CqB,那么C2ij,从而2Aq2B.Ar>B(8) 2=2a2b证：对任意的C,C2<=>CAB<>CACB<=>C2aC2b<z>C2a2bAoBAcBArtB那么2c2A2B且2A2ij=2,故2=2a2b0(9) IAUBIIAI+IBI证：由容斥原理，IAUBI=IAI÷IBI-IABI当ABW时，IAUBI<IAI+IBI当AB=时，IAUBl=IAl+B由知IAUBIIAI+IBIo(10) (B-C)XA=(BXA)-(CXA)证：对任意的有序对(b,a),(b,a)(B-C)×AC)aA<z>(bBb¢C)aA<z>(bBaA)(bCaA)O(b,a)B×AA(b,a)C×A<>(b,a)(BXA)-(CXA)故(B-C)XA(BXA)-(CXA)且(BXA)-(CXA)(B-C)XA那么(B-C)Xa=(BXA)-(CXA)o需要说明的是：对于(b,a)BXA(b,a)任CXA二(bBaA)(b史CAaA)本来，由(b,a)C×A只能得到(aAvbC)o但是(b,a)BXA,故aA,这样，必须b足C。(11)如果AqB,那么8A证：对任意的X,XeBnX史B由于AqB,故xA,即xA°因此，BAo(12) B=AOAUB=U且AB=证：由B=N以及的定义知，AUB=AUA=U,AB=AA=o由ACB=知，对任意的xB,x¢A,即WxB,xA,故BqX。又由AUB=U知，对任意的x,X走A,那么xB,故WqB。这样，B=Ao综合得，B=NoAUB=U且AGB=。(13) AnB=AUB证：对任意的X,AnBOx史(AGB)OXeAVX任BOXEAVXeB<=>x(AUB)那么AC3q)u万且AUBQAnB故AcB=AuBo(14) AuB=AB证：对任意的X,AuBOx史(AUB)OxCAaxeBOXEAAxB<=>x(A月)那么AuBqNn万且ABAuB故ADB=ArB°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设Rl和R2是集合a,b,c,d,e上的二元关系,其中，R=(a,b),(c,d),(b,d),(b,b),(d,e),R2=(a,a),(b,c),(d,c),(e,d),(c,a)求:RiR2,R2R1,R1+,R2+,R1*,R2*解答：RIR2=(a,c),(c,c),(b,c),(d,d)R2R=(a,b),(b,d),(d,d),(e,e),(c,b)Ri+=(a,b),(c,d),(b,d)(b,b),(d,e),(a,d),(a,e),(b.e),(c,e)R2+=(a,a)Xb,c),(d,c),(e,d),(c,a)(b,a),(d,a)Xe5c)5(e,a)Ri*=Ri+U(a,a),(b,b),(c,c),(d,d),(e,e)R2*=R2+U(a,a),(b,b),(c,c),(d,d),(e,e)111.设口=(岫),(备(1),(1),(1)是集合41)4(1同上的二元关系球:(敖雪峰)(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设Rl和R是集合a,b,c,d,e上的二元关系，请证明以下关系。(唐明珠02282084)(1) RiR2*°证明：用反证法，假设叫&=&叫。设K=(a,»,(Gd),&=S,c),3,e)。那么R1R2=(,c),R2R1=(bid)t这与打邑=凡与相矛盾，所以RiR2R2Rio(2) (RR2)R3=RI(R2尺3)。证明:任取(x.,y),其中x,y,b,c,d,e,使得(x,y)w(与用阳<=>z(x,z)R1R2a(z,y)eR3)za,b,c,dye< >3z(x)eRia(Z,z)eR2(zty)R3)tafb,c9d,e< =>-w)A3z(z)eR2(z9y)eR3)< >(x)R八(f,y)R2R3Oay)eRi(R2R3)所以得证(RlR2)&=8(&&)。(3)(RlUR2)&=UR2R3。证明：任取区,丫),其中*,丫4,6,。,乩6,使得(元,丫)(7?&)&。o3z(x,z)RU-2八(z，y)w&)za,b9c,d,e)03z(x,Z)WRIV(xtZ)WR2(z,y)e&)03z(x,Z)WRl八(z9y)ejR3)v3z(x,z)eR2(z,y)R3)< =>(x,y)RR3V(x,y)R2R3O(X,y)&R3U所以得证(KUR2)&=RR3UR2R3(4)&(舄UR2)=R3RUR3R2。证明：任取(x.,y),其中x,y,b,c,d,e,使得(x,y)&(与。&)。< =>3z(x,z)&八(z,y)CRlUR2)za9b,c,d,e)< =>3z(x,z)&八(z,y)&V(z,y)&)03z(x,z)&(z,y)WRl)V3z(x,z)三R3(z9y)eR2)< >(x,y)&凡V(冗，y)eR3R2=(X,y)K3RUR3R2所以得证R3(Rl(JR2)=R3RiUR3R2.(RlR2)R3qR|&l&&。证明：任取(x.,y),其中x,y,1c,d,e,使得(x,y)w(R0凡)&。=>3z(x,z)Ri2(z,y)R3)z三a,b,c9d,e)=>3z(x,z)e7?!a(x,z)eR2(z,y)&)=>3z(x,z)jRi(z,、)&)三2(x,z)eR2(z,y)&)=>(,y)WRIR3八(,y)R2R3=>(xiy')eR1R3HR2R3所以得证出R2*3居.仇。(6)R3(RlR2)R3R.R3R20证明:任取(x.,y),其中x,ya,b,c,d,e,使得(x,y)凡因口此)。=>3z(x,z)eR3(z,y)£R11&)z三a,b,c,d,e=>3z(x,z)eR3(z,y)R八(z,y)&)=>3z(x,z)&(z,y)WRl)A3z(x,z)eR3(z,y)eR2)=>(x,y)eR3R1a(x,y)&&=>(x,y)nR3R2所以得证R式&UR2)=R3R1R3R2.1.13 通常意义下的=是自然数集上的一个等价关系，请按照该等价关系给出自然数集的等价类(02282075冯蕊)“="关系将自然数集N分成无穷多个等价类：0,1,2,3,4,5,6,1.14.在什么样的假设下，人与人之间的“同乡关系"是等价关系。当“同乡关系”在给定的限定下成为等价关系时，它将所有的中国人分成什么样的等价类？（吴玉涵02282091）答：假设出生在同一个省的关系为同乡关系。按照这样的同乡关系将中国人按照出生省份的不同划分出等价类。1.16 Z*上的二元关系RL定义为：对任给的x,yZ*,如果对于VzZ*,均有xzL与yzL,同时成立或者同时不成立，那么XRLyo(周期律02282067)证明：(1)对于VaZ*xzL与xzL显然是同时成立或同时不成立，对于VZZ*,故XRLX，RL具有自反性。对于Vx,yZ*,如果XRLy,故xzL与yzL同时成立或同时不成立，显然故yzL与xzL同时成立或同时不成立，故yRlx,Rl具有对称性。对于WX,y,p£Z*,如果XRLy,yRu故xzL与yzL同时成立或同时不成立，并且故yzL与pzL同时成立或同时不成立，故xz£与pzL同时成立或同时不成立，故XRLp,故RL具有传递性。综上，关系RL是在Z*上的等价关系。(2)如果对于任给的x,yZ*,如果XRLy，故对于VzZ*,xzL与yzL同时成立或同时不成立，对于VpZ*,如果xzp"因为zpZ*,又因为XRLy,故yzpL,同理，可以证明如果XZPeL,因为zpZ*,又因为XRLy,故yzp史L,因此，对于DPg*,xzpL与yzpL同时成立或同时不成立，故如果对于任给的,y6Z*,如果XRLy，那么必有XZRLyz。综上，该关系的等价性和右不变性均得以证明。1.17 设0,l*上的语言L=()nimn,m20,请给出0,l*关于L所确定的等价关系RL的等价设L是上的一个语言,*上的二元关系Rl定义为:对任给的x,y*,如果对于Vz*,均有xzL与yzL同时成立或者同时不成立,那么XRLy.根据上述定义可知，0)"关于L所确定的等价关系Rl的等价类有三个.(1) Vx,ynimn20,m>0,都有Vz*，均有xzL与yzL同时成立或者同时不成立(只看苗zPn20的时候,才同时成立,否那么不最立)(2) Vx,yninn20,m=0,都有Dz，均有xzL与yzL同时成立或者同时不成立(只有当z(yT"n,m20的时候才同时成立,否那么不成立)(3) Vx,y任0Tn,m20,都有Vz*，均有xzL与yzL同时成立或者同时不成立(无论Z取何值,都不同时成立)三个等价类为ni7n20,m>0(Onlmln2o,m=O和除此之外的0,l*上的字符1.18也确定的0,1*的等价分类为：10=xl0yx,y0,1*)Unl0=0mIm-n=0=0nlnn>01 =0mlnm-n=l2 =0mlnm-n=2h=Oralnm-11=h其中，n,m均为非负整数。1.19.给出以下对象的递归定义(02282072褚颖娜)1 .n个二元关系的合成(1) R1R2=(a,c)3(a,b)Rl且玉b,c)R2)RiR2Rn=(d,g)3(d,e)RR2Rn.且文f,g)R11)2 .无向图中路的长度在无向图G中，假设两顶点VbV2之间存在一条无向边，那么VbV2是G的一条长位1的路假设V,V2Vnd为一条长度为kl的路,且Vnl,Vn存在一条无向边,那么V1,VlVnl,Vn为G的一条长度为k的路3 .有向图中路的长度在有向图G中，假设两顶点V,V2之间存在一条有向边，那么VI,V2是G的一条长位1的路假设V,V2Vnd为一条长度为kl的路,且Vnl,Vn存在一条有向边,那么V1,VlVnl,Vn为G的一条长度为k的路4 .n个集合的乘积S1×S2=(a,b)aSl且bSzS×SzSn=(d,e)dSlXSzSn.且ewS>5 .字母a的n次暴(1) a0=l;(2) an=a,a;6 .字符串X的倒序假设X为单字符，那么X的倒序是它本身假设X的倒序为y,假设X后跟-字符a,那么xa的倒序为ay;7 .字符串X的长度假设X为空串£,那么冈二0;假设字符串X的长度为k,其xa或ax的长度为k+18 .自然数。为自然数，如果X为自然数，那么X+1为自然数L20.使用归纳法证明以下各题。(吴玉涵 02282091)0 + + +1 nH=(w + 1) n + 证明:(1) n=l时,一=-成立1×2 1+1(2)假设n=k时成立,W-L÷-L÷-L÷1×2 2×3 3×4 -Z + 1) k + n = + l,-+ + + +! +!1×2 2×3 3x4n(n + ) (/? + !)(/? + 1 + 1)n1-+ + 1 (/? + 1)(/?+ 1 + 1)_ ( + l + l) + l5 +1)( +1 + 1) h + 1"( + l)÷l所以 =Z +1时成立(3)由归纳原理，对任一nN-0都成立(2)w4W,2no证明：(1)当=4时2 =16 = 4?成立(2)假设4时成立，P2k=2当 = k + l时，2l=2×2k2k2由Z4知,22(k+iy所以，2k"" + l)2, = & +耐成立。(3)由归纳原理，Vn 4 => 2n n2(3)当45为有穷集合时,AxB=H跳证明：设IAl=,忸I=ZW(1)当n=0,m=0时,AXBl=I0x0=O=AllMSn=O,mOH,A×B=0×B=O=AB当nw,m=Of,A×B=A×0=O=AB(2)假设m0,n=k时成立，BPA×B=AB=mn=mk当=Z+1时，令A=AU,A11a=0AxB=(A,a)×B=A,xB0×B=A'×B+×B=+w=m(jl+l)所以，=女+1时,AXM=IA同同理，当工0,m=k成立时，m=k+l也成立(3)由归纳原理，当48为有穷集合时,4xM=MM成立。(4)设A,B是有穷集合，则从A到B的映射有IBF个。证明：设IAl=zzLB=ml(1)当n=l,m=l时，从A到B的映射有阿阳=1个，成立(2)假设n=k时成立，即从A到B的映射有IBr=W个当=Z+1时，设A=AU4,A'0=0,A'=%从A到B的映射就是从AL到耶J映射，从4到硼映射个数为忸同=/个，从到相勺映射个数为m个，所以从AU到相勺映射的个数为心"=产(3)由归纳原理，A,B是有穷集合，则从A到B的映射有IBF个。(5)G=(V,E)为一个无向图，贝hdeg(v)=2Eover证明：(1)V=ltt,E=0,_deg(v)=2E=O成立。vV(2)设团二加假设M=Q时成立,即UdegU)=2因=26当M=+1时，设V=VU%,V%=0,Udeg")=2E=2加vV,若与0Z个结点相连，则增加边数hdeg(%)=h对于个结点增加度数也为h所以，,deg(y)=2El+2%=2(w+B=2EveV(3)由归纳原理，G=(V,E)为一个无向图，则UdegW)=2因。(6)G=(V,E)为一个有向图，则U,deg(u)=Iodeg=固。veVveV证明：(I)M=I时,IEl=O,jZdeg(V)=Uodege)=0=因成立v6VveV(2)设园二团，假设M=">0H寸成立，即Jidegw)=U0deg(u)=|同成立VGVVV当M="+1时，设V=V,jv0,V11v0=0,1zdeg(v)=UOdegW)=IEI=ZWvV,vV,设ideg(%)=p,odeg(v0)=则Uideg(IO=ideg(y)+ideg(%)=(E+q)+p=因v6VveV''UOdegW=Uydege)+odeg(%)=(|矶+p)+q=|目veVvV'',(3)由归纳原理，当G=(V为一个有向图时，zdeg(v)=ldeg(v)=EvVvV11(7)一个高度为+1的二元树的根结点到叶子的最大路长是n,该树最多含有211个叶子证明：(1)高度为2时，最多有21=2个叶子，成立(2)假设高度为n+1时成立，即最多有叶子2"个当高度为n+2时，第n+1层上最多有结点2。个，则第n+2层上最多有叶子为2×2n=2.个(3)由归纳原理，高度为n+1的二元树最多含有2"个叶子(8)根据1.4.3节中的相关定义，对字母表2中的任意字符串anal,=an+m证明：(1)n=0,m=0时，a°aQ=成立(2)假设n=p,m=q时成立,即炉炉=当n=p+Lm=qD'J,aiaq=aaaa=aaaaa-aaaaap+l个q个,个q个P个q个=p+q=p+q+1同理有，n=p,m=q+l成立(3)由归纳原理,a%"*=。""成立。(9)对字母表Z中的任意字符串X,X的前缀有冈+1个。证明：(1)X=O,即x=£时，X的前缀只有它本身，有卜1+1=1个，成立(2)假设x=n时成立,即X的前缀有x+lr+l个。当IXbn+1时，设X=XbX的前缀有n+1个。X中含有b的前缀只有一个，所以X的前缀有n+1+l个(3)由归纳原理，对字母表Z中的任意字符串X,X的前缀有冈+1个。1. 21以下集合中哪些是字母表。(l)l,2)o(2)a,b,c,.,z)o(3)(4) (a,b,a,co(5) 0,1,2,3,.,n,.)o(6) a,d,fCa,b,c.,z。解答：字母表为(1)(2)(6)(3)不满足字母表的非空性，(4)不满足字母表的可区分性，(5)是无穷集合不满足字母表的有穷性。22 .设Z=a,b,求字符串aaaaabbbba的所有前缀的集合，后缀的集合，真前缀的集合,真后缀的集合。(吴贤培02282047)解：(1)前缀：,a,aa,aaa,aaaa,aaaaa,aaaaab,aaaaabb,aaaaabbb,aaaaabbbb,aaaaabbbba)(2)后缀:(,a,ba,bba,bbba,bbbba,abbbba,aabbbba,aaabbbba,aaaabbbba,aaaaabbbba(3) 真前缀:,a,aa,aaa,aaaa,aaaaa,aaaaab,aaaaabb,aaaaabbb,aaaaabbbb)(4)真后缀：,a,ba,bba,bbba,bbbba,abbbba,aabbbba,aaabbbba,aaaabbbba23 .=aa,ab,bb,ba),求字符串aaaaabbbba的所有前缀的集合、后缀的集合、真前缀的集合、真后缀的集合。(02282023郭会)解：由前缀、后缀、真前缀、真后缀的集合可以有：其前缀集合为：,aa,aaaa,aaaaab,aaaaabbb,aaaaabbbba)其真前缀集合为：£,aa,aaaa,aaaaab,aaaaabbb其后缀集合为：£,ba,bbba,abbbba,aaabbbba,aaaaabbbba)其其后缀集合为：,ba,bbba,abbbba,aaabbbba1.25抽象技术为什么对计算机技术特别重要？(段季芬)对于计算机技术方面的人来说，计算思维能力是必需的，这是学科本身决定的。计算机科学与技术学科所要解决的根本问题是什么能被有效的自动化。现代计算机技术认为，要想有效的实现自动化，必须经过抽象进行形式化。1. 26为什么要求字母表示非空有穷集？(唐明珠02282084)解答：字母表是非空有穷集合，由字母表中的元素连接而成的字符串叫做字母表上的句子。假设字母表为空集，那么字母表中唯一的元素就是£,而£不管如何组合，其组成的句子都为空，其研究就失去了意义，所以字母表要具有非空性。1.27. 考虑一下,为什么要研究句子的前缀,后缀？解：形式语言是研究自然语言和人工语言的数学工具，只研窕组成规那么，不研究语义。而我们将语言看做句子的集合,句子看做字母按照一定规那么组成的字符串,故主要根据规那么的形式区分语言类,大局部问题都可转化为判定某个句子是否属于某个语言的问题.而这就要求从一个句子的结构出发,而一个整体的句子在结构上将其划成几个局部,对于我们的研究会有很大的帮助.事实上研究句子的前缀,后缀,也就是为了将句子结构进行有意识的划分而更加方便的研究句子,看其是否符合某个形式语言的组成规那么.28.令=l,0,以下语言在结构上有什么样的特点？(吴贤培02282047)乙=0"nInlo解：该语言的每一个句子由二局部构成，这二局部的组成依次为：0.Io其中，每局部的0或1的个数相等，且都不小于1个。<2)L2=nlmI11,mlo解：该语言的每一个句子由二局部构成，这二局部的组成依次为：0.Io其中，每局部的0或1的个数不一定相等，但都不小于1个。乙=0Tonln21。解：该语言的每一个句子由三局部构成，这三局部的组成依次为：0、1、Oo其中，每局部的。或1的个数相等，且都不小于1个。(4)y4=OnnOkIn,m,k&l)o解：该语言的每一个句子由三局部构成，这三局部的组成依次为：0、1、Oo其中，每局部的。或1的个数不一定相等，但都不小于1个。LS=0nl%nIn0)解：该语言的每一个句子由三局部构成，这三局部的组成依次为：0、1、Oo其中，每局部的。或1的个数相等，并且可以都为0。L6=x3TIX,3kIo解：该语言的每一个句子从前向后看和从后向前看时，有一局部是对称相等的。而且，这对称相等的两个串中间一定有另外一个串。L7=xT3IX,+。解：该语言的特点是在其句子中一定可以找到这样的一个串：该串是从句子的第一个字符开始的连续的串，且紧跟该串之后的连续一段字符串恰好是该串从后往前看是的那个串，而且这样的两个串之后一定还有另外一个字符串。Lg=aaaZ,S.+。解：该语言的每一个句子有这样的特点：该句子的第一个字符和最后一个字符都是O或都是1,且该句子的长度不小于3。(9)=,0,1,11,01,10,11,000,>解：该语言的句子是所有由0和1构成的串，包括空串£。(10)Zylo=0,l,00,01,10,ll,000,o解：该语言的句子是所有由。和1构成的串，不包括空串1.29设LLL2,L3,L4分别是Z1,Z2,23,E4上的语言，能否说LLL2,L3,L4都是某个字母表上的语言？如果能，请问这个字母表是怎么样的？(刘桂02282083)答：能=1U2U3U41.30设4,&,右，乙分别是一2,工，£上的语言，证明下面的等式成立。ZqU%&U。设VaL1JL2,=>«L或eL2=>ae或WLl=>Va£，故原式得证L1U(L2Uz3)=(L1JL2)IjL3设VLU(L2U4)ncL曲£4曲4=WLlU(L2J4)故，原式得证W")*=如果Ll=,(L*)*=LJ如果LlW，假设=M2a,J,八l,那么=,al,a2.n,aiai9aia2.lan.,而(Lj)*=,ax,a2.an,axa