1、第一章参考答案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、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中的元素为Ai（i=1,2,3,），Ai也是集合，Ai中的元素在110之间，并且和为10。根据集合元素的彼此可区分性，可以计算出Ai中元素的最多个数，方法是：把1开始的正整数逐个相加，直到等于10（即10=1+2+3+4），这样，Ai中最多有4个元素。原因是：从最小的1开始，每次加入新的元素都只依次增加1，这样相加的和最小，要加到10，元素个数就最多。求出最大的Ai4后，再求出元素个数为3，
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）
4、 所有基数不大于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）如
5、果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|0,都有z*,均有xzL与yzL同时成立或者同时不成立(只有当z1n|n0的时候,才同时
6、成立,否则不成立)(2) x,y0n1m|n0,m=0,都有z*,均有xzL与yzL同时成立或者同时不成立(只有当z0n1m|n,m0的时候,才同时成立,否则不成立)(3) x,y0n1m|n,m0,都有z*,均有xzL与yzL同时成立或者同时不成立(无论z取何值,都不同时成立)三个等价类为0n1m|n0,m00n1m|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=2.h=0m1n|m-n=h.其中，n，m均为非负整数。1.19
7、.给出下列对象的递归定义 (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的路，且v
8、n-1,vn存在一条有向边，则v1，v2vn-1,vn为的一条长度为k的路4 n个集合的乘积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, 若x后跟一字符a, 则xa的倒序为ay;7 字符串x的长度若x为空串e，则|x|=0;若字符串x的长度为k,其xa或ax的长度为k+18 自然数0为自然数，如果x为自然数，则x+1为自然数1.20.使用归纳法证明下列各题。 (吴玉涵 02282091)121下列集合中哪些是字
9、母表。 (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,
10、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的所有前缀的集合、后缀的集合、真前缀的集合、真后缀的集合。 （02282015 郭会）解：由前缀、后缀、真前缀、真后缀的集合可以有：其前缀集合为：,aa,aaaa,aaaaab,aa
11、aaabbb,aaaaabbbba其真前缀集合为：,aa,aaaa,aaaaab,aaaaabbb其后缀集合为：,ba,bbba,abbbba, aaabbbba, aaaaabbbba 其真后缀集合为：,ba,bbba,abbbba, aaabbbba1.25抽象技术为什么对计算机技术特别重要？ （段季芬）对于计算机技术方面的人来说，计算思维能力是必需的，这是学科本身决定的。计算机科学与技术学科所要解决的根本问题是什么能被有效的自动化。现代计算机技术认为，要想有效的实现自动化，必须经过抽象进行形式化。126 为什么要求字母表示非空有穷集？ （唐明珠 02282084）解答：字母表是非空有穷集
12、合，由字母表中的元素连接而成的字符串叫做字母表上的句子。假设字母表为空集，则字母表中唯一的元素就是不论如何组合，其组成的句子都为空，其研究就失去了意义，所以字母表要具有非空性。1.27. 考虑一下,为什么要研究句子的前缀,后缀?解: 形式语言是研究自然语言和人工语言的数学工具，只研究组成规则，不研究语义。而我们将语言看做句子的集合,句子看做字母按照一定规则组成的字符串,故主要根据规则的形式区分语言类,大部分问题都可转化为判定某个句子是否属于某个语言的问题.而这就要求从一个句子的结构出发,而一个整体的句子在结构上将其划成几个部分,对于我们的研究会有很大的帮助.事实上研究句子的前缀,后缀,也就是为
13、了将句子结构进行有意识的划分而更加方便的研究句子,看其是否符合某个形式语言的组成规则.28令1, 0，下列语言在结构上有什么样的特点？（吴贤珺 02282047）0n1nn1。解：该语言的每一个句子由二部分构成，这二部分的组成依次为：0、1。其中，每部分的0或1的个数相等，且都不小于1个。0n1mn, m1。解：该语言的每一个句子由二部分构成，这二部分的组成依次为：0、1。其中，每部分的0或1的个数不一定相等，但都不小于1个。0n1n0nn1。解：该语言的每一个句子由三部分构成，这三部分的组成依次为：0、1、0。其中，每部分的0或1的个数相等，且都不小于1个。0n1m0kn, m, k1。解：
14、该语言的每一个句子由三部分构成，这三部分的组成依次为：0、1、0。其中，每部分的0或1的个数不一定相等，但都不小于1个。0n1n0nn0。解：该语言的每一个句子由三部分构成，这三部分的组成依次为：0、1、0。其中，每部分的0或1的个数相等，并且可以都为0。xxTx, 。解：该语言的每一个句子从前向后看和从后向前看时，有一部分是对称相等的。而且，这对称相等的两个串中间一定有另外一个串。x xTx, 。解：该语言的特点是在其句子中一定可以找到这样的一个串：该串是从句子的第一个字符开始的连续的串，且紧跟该串之后的连续一段字符串恰好是该串从后往前看是的那个串，而且这样的两个串之后一定还有另外一个字符串
15、。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）如果如
16、果，假设则，而故，原式得证（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上的语言，证明下列等式成立否 (段季芬)（1）（L1L2）*=（L2L1）*不成立 例如： L1=a，L2=b，则（L1L2）*=（ab）*=，ab,abab,a
17、babab,. 而（L2L1）*=（ba）*=,ba.baba,bababa,. 显然不等。（2）L1+=L1+L1+不成立 例如： L1=0，那么L1+=L1UL12UL13U。=0，00，000，。而L1+L1+=00，000，0000，。，比L1+少基本项L1 可得知L1+L1+是L1+的子集 （3）L1*=L1*L1*正确因为L1*L1*=（L10UL1UL12UL13U。）（L10UL1UL12UL13U。） =（L10UL1UL12UL13U。）L10U（L10UL1UL12UL13U。）L1U。 =（L10UL1UL12UL13U。）UAUBU。 从观察可知A是（L10UL1UL
18、12UL13U。）的真子集，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=L1（L2L1UL1）*正确（3） L2（L1L2UL2）*L1=L1L1*L2（L1L1*L2）*不正确假设L1=a，L2=b，L2（L1L2UL2）*L1表示的语言肯定以b打头，而L1
19、L1*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，。由于（L10U
20、L1UL12UL13U。）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。（后面的项都被第一项吸收） =（L1UL12UL13U。）=L1+ 同理可证得L1+L1*=L1+1.32 设，请给出上的下列语言的形式表示。
