形式语言与自动机理论蒋宗礼第一章参考复习资料[002].docx

第一章参考答案1.1请用列举法给出以下集合。 吴贤珺 02282047 你知道的各种颜色。解：红，橙，黄，绿，青，蓝，紫 大学教师中的各种职称。解：助教，讲师，副教授，教授 你所学过的课程。解：语文，数学，英语，物理，化学，生物，历史，地理，政治 你的家庭成员。解：父亲，母亲，妹妹，我 你知道的所有交通工具。解：汽车，火车，飞机，轮船，马车 字母表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 所有的非负奇数。解：1,3,5,7, 0100的所有正整数。解：1,2,3,100(10) 110之间的和为10的整数集合的集合。解：设所求的集合为A，集合A中的元素为Aii=1,2,3,，Ai也是集合，Ai中的元素在110之间，并且和为10。根据集合元素的彼此可区分性，可以计算出Ai中元素的最多个数，方法是：把1开场的正整数逐个相加，直到等于10即10=1+2+3+4，这样，Ai中最多有4个元素。原因是：从最小的1开场，每次参加新的元素都只依次增加1，这样相加的和最小，要加到10，元素个数就最多。求出最大的Ai4后，再求出元素个数为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） 所有基数为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，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 刘秋雯1A=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,存在一个集合C 使B=AC 且AC为空集那么|B|=|A|+|C|C|=0|A|=|B|3如果A为B的真子集，那么|A|=|B|证明：1当A为有穷集合时，因为A为B的真子集，且那么对于任何xA有xB,且存在B的x，此x不A存在一个非空集合C ， 使B=AC 且AC为空集那么|B|=|A|+|C| 且|C|=1|A|B|2当A为无穷集合，因为A为B的真子集，那么B一定也为无穷集合，|A|，|B|A|=|B|综合1，2所述，|A|<=|B|4如果A是有穷集且A为B的真子集那么|A|B|证明：见上题证明15如果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的子集 那么对于任何xA，那么x都B，且，又对于任何yB，那么yC，对于任何xA，xCA为C的子集8如果A为B的真子集，B为C的真子集，那么A为C的真子集 证明： A为B的真子集，B为C的真子集 那么对于任何xA，那么x都B，且，存在xB但次x不A，又对于任何yB，那么yC，存在yC但此y不B，对于任何xA，xC，存在xC.x不AA为C的真子集9如果A为B的子集，B为C的真子集，那么A为C的真子集 证明： 因为A为B的子集，B为C的真子集 那么对于任何xA， x都B，且x都C又对于任何yB，那么yC，存在yC但此y不B，那么y不A对于任何xA，xC，存在xC.x不AA为C的真子集10如果A为B的真子集，B为C的子集，那么A为C的真子集 证明： A为B的真子集，B为C的子集 那么对于任何xA，那么x都B，且存在xB但次x不A，又对于任何yB，那么yC对于任何xA，xC，存在xC.x不AA为C的真子集11如果A=B，那么|A|=|B|证明： A=B，那么A及B所含元素一样|A|=|B|12如果A为B的子集，B为C的真子集，或如果A为B的真子集，B为C的子集，那么A为C的真子集证明：证明见9，101.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,50,7,8,90,7,8,9= 0,1,3,5,7,8,9 = (7).(8).=1，2，3，4，5，618 对论域U上的集合A、B、C，证明以下结论成立。 02282047 吴贤珺 ABBA证：对任意的x，xAB xAxB xBxA xBA故ABBA 且 BAAB那么 ABBA。 (AB)CA(BC)证：对任意的x，x(AB)C x(AB)xC (xAxB)xC xAxBxCxA(xBxC)xAx(BC )xA(BC) 故(AB)C A(BC) 且 A(BC) (AB)C 那么 (AB)CA(BC)。 ABA iff BA证： 由BAB及 ABA知 BA。 由BA 知xB, xA 那么对任意的x，xABxAxBxA 故 ABA，又AAB，所以 ABA。综合得到 ABA iff BA。 A×(BC)(A×B)(AC)证：对任意的有序对(a, b)，(a, b)A×(BC) aAb(BC) aA(bBbC) (aAbB)( aAbC)(a, b)A×B(a, b)A×C(a, b)(A×B)(A×C) 故A×(BC) (A×B)(AC) 且 (A×B)(AC) A×(BC) 那么 A×(BC)(A×B)(AC)。 (BC)×A(B×A)(C×A)证：对任意的有序对(b, a)，(b, a)(BC)×A b(BC)aA (bBbC)aA (bBaA)(bCaA)(b, a)B×A(b, a)C×A(b, a)(B×A)(C×A) 故(BC)×A (B×A)(C×A) 且 (B×A)(C×A) (BC)×A 那么 (BC)×A(B×A)(C×A)。 A×(BC)(A×B)(A×C)证：对任意的有序对(a, b)，(a, b)A×(BC) aAb(BC) aA(bBbC) (aAbB)( aAbC)(a, b)A×B(a, b)A×C(a, b)(A×B)(A×C) 故A×(BC) (A×B)(AC) 且 (A×B)(AC) A×(BC) 那么 A×(BC)(A×B)(AC)。 需要说明的是：对于 (a, b)A×B(a, b)A×C (aAbB)( aAbC 本来，由(a, b)A×C 只能得到 (aAbC)。但是(a, b)A×B，故aA，这样，必须bC。 如果 AB，那么2A2B 证：对任意的C，C2A CA 由于AB，故CB，那么C2B，从而2A2B。 22A2B证：对任意的C，C2 CAB CACB C2AC2B C2A2B那么 2 2A2B 且 2A2B 2，故22A2B。 ABAB证：由容斥原理，ABABAB 当AB时，ABAB 当AB时，ABAB 由知ABAB。(10) (BC)×A(B×A)(C×A)证：对任意的有序对(b, a)，(b, a)(BC)×A b(BC)aA (bBbC)aA (bBaA)(bCaA)(b, a)B×A(b, a)C×A(b, a)(B×A)(C×A) 故 (BC)×A (B×A)(C×A) 且 (B×A)(C×A) (BC)×A 那么 (BC)×A(B×A)(C×A)。 需要说明的是：对于 (b, a)B×A(b, a)C×A (bBaA)(bCaA) 本来，由(b, a)C×A 只能得到 (aAbC)。但是(b, a)B×A，故aA，这样，必须bC。(11) 如果AB，那么证：对任意的x，xxB 由于AB，故xA，即x。因此，。(12) BABU且AB证： 由B 以及的定义知，ABAU，ABA。 由AB知，对任意的xB，xA，即xB，x，故B。 又由ABU知，对任意的x，xA ，那么xB，故B。 这样，B。综合得，BABU且AB。 (13) 证：对任意的x，x x(AB) xAxB xx x() 那么 且 故。(14) 证：对任意的x，x x(AB) xAxB xx 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 设R1和R2是集合a,b,c,d,e上的二元关系,其中,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.设R=(a,b),(c,d),(b,d)是集合a,b,c,d,e上的二元关系,求: 敖 雪 峰(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).112 设和是集合a,b,c,d,e上的二元关系，请证明以下关系。 (唐明珠 02282084)(1) 。 证明：用反证法，假设。设。 那么 这及相矛盾， 所以。(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 通常意义下的=是自然数集上的一个等价关系，请按照该等价关系给出自然数集的等价类 02282075 冯蕊“=关系将自然数集N分成无穷多个等价类：0，1，2，3，4，5，6，1.14.在什么样的假设下，人及人之间的“同乡关系是等价关系。当“同乡关系在给定的限定下成为等价关系时，它将所有的中国人分成什么样的等价类？ (吴玉涵 )答：假设出生在同一个省的关系为同乡关系。按照这样的同乡关系将中国人按照出生省份的不同划分出等价类。1.16 上的二元关系RL 定义为：对任给的x,y，如果对于，均有xz及yzL，同时成立或者同时不成立，那么xRLy。 (周期律 02282067)证明：1对于 xz及xzL显然是同时成立或同时不成立，对于，故xRLx，RL 具有自反性。 对于，如果xRLy, 故xz及yzL同时成立或同时不成立，显然故yz及xzL同时成立或同时不成立，故yRLx, RL 具有对称性。 对于,如果xRLy, yRLp, 故xz及yzL同时成立或同时不成立，并且故yz及pzL同时成立或同时不成立，故xz及pz同时成立或同时不成立，故xRLp，故RL具有传递性。 综上，关系RL是在上的等价关系。2如果对于任给的x,y，如果xRLy， 故对于，xz及yzL同时成立或同时不成立， 对于,如果xzp,因为zp,又因为xRLy, 故yzpL，同理，可以证明如果xzp,因为zp,又因为xRLy, 故yzpL， 因此，对于，xzp及yzpL同时成立或同时不成立， 故如果对于任给的x,y，如果xRLy，那么必有xzRLyz。综上，该关系的等价性和右不变性均得以证明。1.17 设0,1*上的语言L=0n1m|n,m0,请给出0,1*关于L所确定的等价关系RL的等价类. 设L是上的一个语言,*上的二元关系RL定义为:对任给的x,yÎ*,如果对于"zÎ*,均有xzÎL及yzÎL同时成立或者同时不成立,那么xRLy.根据上述定义可知, 0,1*关于L所确定的等价关系RL的等价类有三个.(1) "x,yÎ0n1m|n0,m>0,都有"zÎ*,均有xzÎL及yzÎL同时成立或者同时不成立(只有当zÎ1n|n0的时候,才同时成立,否那么不成立)(2) "x,yÎ0n1m|n0,m=0,都有"zÎ*,均有xzÎL及yzÎL同时成立或者同时不成立(只有当zÎ0n1m|n,m0的时候,才同时成立,否那么不成立)(3) "x,yÏ0n1m|n,m0,都有"zÎ*,均有xzÎL及yzÎL同时成立或者同时不成立(无论z取何值,都不同时成立)三个等价类为0n1m|n0,m>00n1m|n0,m=0和除此之外的0,1*上的字符1.18 RL确定的0，1*的等价分类为： 10=x10y|x,y0,1*1n|n1 0=0m1n|m-n=0=0n1n|n0 1=0m1n|m-n=12=0m1n|m-n=2h=0m1n|m-n=h其中，n，m均为非负整数。1.19.给出以下对象的递归定义 (02282072 褚颖娜)1 n个二元关系的合成(1) R1R2=(a,c)|$(a,b)Î R1且$(b,c) Î R2(2) R1R2Rn = (d,g)|$(d,e)ÎR1R2 Rn-1且$(f,g) Î Rn 2 无向图中路的长度在无向图中，假设两顶点v1,v2之间存在一条无向边，那么v1,v2是的一条长位的路假设v1,v2vn-1为一条长度为k-1的路，且vn-1,vn存在一条无向边，那么v1，v2vn-1,vn为的一条长度为k的路3 有向图中路的长度在有向图中，假设两顶点v1,v2之间存在一条有向边，那么v1,v2是的一条长位的路假设v1,v2vn-1为一条长度为k-1的路，且vn-1,vn存在一条有向边，那么v1，v2vn-1,vn为的一条长度为k的路4 n个集合的乘积S1´S2=(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, 假设x后跟一字符a, 那么xa的倒序为ay;7 字符串x的长度假设x为空串e，那么|x|=0;假设字符串x的长度为k,其xa或ax的长度为k+18 自然数0为自然数，如果x为自然数，那么x+1为自然数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)不满足字母表的可区分性，(5)是无穷集合不满足字母表的有穷性。22设a, b，求字符串aaaaabbbba的所有前缀的集合，后缀的集合，真前缀的集合，真后缀的集合。 吴贤珺 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，求字符串aaaaabbbba的所有前缀的集合、后缀的集合、真前缀的集合、真后缀的集合。 郭会解：由前缀、后缀、真前缀、真后缀的集合可以有：其前缀集合为：,aa,aaaa,aaaaab,aaaaabbb,aaaaabbbba其真前缀集合为：,aa,aaaa,aaaaab,aaaaabbb其后缀集合为：,ba,bbba,abbbba, aaabbbba, aaaaabbbba 其真后缀集合为：,ba,bbba,abbbba, aaabbbba1.25抽象技术为什么对计算机技术特别重要？ 段季芬对于计算机技术方面的人来说，计算思维能力是必需的，这是学科本身决定的。计算机科学及技术学科所要解决的根本问题是什么能被有效的自动化。现代计算机技术认为，要想有效的实现自动化，必须经过抽象进展形式化。126 为什么要求字母表示非空有穷集？ 唐明珠 02282084解答：字母表是非空有穷集合，由字母表中的元素连接而成的字符串叫做字母表上的句子。假设字母表为空集，那么字母表中唯一的元素就是不管如何组合，其组成的句子都为空，其研究就失去了意义，所以字母表要具有非空性。1.27. 考虑一下,为什么要研究句子的前缀,后缀?解: 形式语言是研究自然语言和人工语言的数学工具，只研究组成规那么，不研究语义。而我们将语言看做句子的集合,句子看做字母按照一定规那么组成的字符串,故主要根据规那么的形式区分语言类,大局部问题都可转化为判定某个句子是否属于某个语言的问题.而这就要求从一个句子的构造出发,而一个整体的句子在构造上将其划成几个局部,对于我们的研究会有很大的帮助.事实上研究句子的前缀,后缀,也就是为了将句子构造进展有意识的划分而更加方便的研究句子,看其是否符合某个形式语言的组成规那么.28令1, 0，以下语言在构造上有什么样的特点？吴贤珺 022820470n1nn1。解：该语言的每一个句子由二局部构成，这二局部的组成依次为：0、1。其中，每局部的0或1的个数相等，且都不小于1个。0n1mn, m1。解：该语言的每一个句子由二局部构成，这二局部的组成依次为：0、1。其中，每局部的0或1的个数不一定相等，但都不小于1个。0n1n0nn1。解：该语言的每一个句子由三局部构成，这三局部的组成依次为：0、1、0。其中，每局部的0或1的个数相等，且都不小于1个。0n1m0kn, m, k1。解：该语言的每一个句子由三局部构成，这三局部的组成依次为：0、1、0。其中，每局部的0或1的个数不一定相等，但都不小于1个。0n1n0nn0。解：该语言的每一个句子由三局部构成，这三局部的组成依次为：0、1、0。其中，每局部的0或1的个数相等，并且可以都为0。xxTx, 。解：该语言的每一个句子从前向后看和从后向前看时，有一局部是对称相等的。而且，这对称相等的两个串中间一定有另外一个串。x xTx, 。解：该语言的特点是在其句子中一定可以找到这样的一个串：该串是从句子的第一个字符开场的连续的串，且紧跟该串之后的连续一段字符串恰好是该串从后往前看是的那个串，而且这样的两个串之后一定还有另外一个字符串。aaa,。解：该语言的每一个句子有这样的特点：该句子的第一个字符和最后一个字符都是0或都是1，且该句子的长度不小于3。 ,0,1,11,01,10,11,000,。解：该语言的句子是所有由0和1构成的串，包括空串。0,1,00,01,10,11,000,。解：该语言的句子是所有由0和1构成的串，不包括空串。1.29设L1，L2，L3，L4分别是1,2,3,4上的语言，能否说L1，L2，L3，L4都是某个字母表上的语言？如果能，请问这个字母表是怎么样的？刘钰 02282083答：能 =12341.30 设分别是上的语言，证明下面的等式成立。1设故原式得证2设故，原式得证3如果如果，假设那么，而故，原式得证4如果如果，假设那么，而故，原式得证5故，原式得证6故，原式得证7故，原式得证8设那么，因此，当k=1,2,n又因为故因此同理可证综上故，原式得证9当时，原式显然成立当时，设因为所以故，原式得证10因为，所以，故，原式得证11设那么，因此，当k=1,2,n又因为故因此同理可证综上故，原式得证12由8小题结论可以推得故，原式得证1.31设L1，L2，L3，L4分别是1，2，3，4上的语言，证明以下等式成立否 (段季芬)1L1L2*=L2L1*不成立 例如： L1=a，L2=b，那么L1L2*=ab*=，ab,abab,ababab,. 而L2L1*=ba*=,ba.baba,bababa,. 显然不等。2L1+=L1+L1+不成立 例如： L1=0，那么L1+=L1UL12UL13U。=0，00，000，。而L1+L1+=00，000，0000，。，比L1+少根本项L1 可得知L1+L1+是L1+的子集3L1*=L1*L1*正确因为L1*L1*=L10UL1UL12UL13U。L10UL1UL12UL13U。 =L10UL1UL12UL13U。L10UL10UL1UL12UL13U。L1U。 =L10UL1UL12UL13U。UAUBU。 从观察可知A是L10UL1UL12UL13U。的真子集，B 是A的真子集，推知后面一项为哪一项前面的一项的真子集，根据吸收规那么所以原式=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*项 肯定不等（2） L1L2UL1*L1=L1L2L1UL1*正确（3） L2L1L2UL2*L1=L1L1*L2L1L1*L2*不正确假设L1=a，L2=b，L2L1L2UL2*L1表示的语言肯定以b打头，而L1L1*L2L1L1*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。UL1UL12UL13U。 =L10UL1UL12UL13U。L1UL10UL1UL12UL13U。L12U。 =L1UL12UL13U。UL12UL13UL14。U。后面的项都被第一项吸收 =L1UL12UL13U。=L1+ 同理可证得L1+L1*=L1+1.32 设，请给出上的以下语言的形式表示。 (1) 所有以0开头的串。 解答：。(2) 所有以0开头，以1结尾的串。 解答：。(3) 所有以11开头，以11结尾的串。 解答：。(4) 所有最多有一对连续的0或者最多有一对连续的1的串。 解答：。(5) 所有最多有一对连续的0并且最多有一对连续的1的串。 解答：按照实际情况分成4类：1) 只有一对连续的0： 。2) 只有一对连续的1：。3) 没有连续的0并且没有连续的1：。4) 有一对连续的0和一对连续的1： (6) 所有长度为偶数的串。 解答： 7所有长度为奇数的串解答：0,1,n=1,2 (8) 所有包含子串01011的串。 解答：。(9) 所有包含3个连续0的子串。 解答：0,1*0000,1*(10) 所有不包含3个连续0的串。 解答：001，01，1。(11) 所有正数第10个字符是0的串。 解答：。(12) 所有倒数第10个字符是0的串。 解答：0,100,1。 第 18 页