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

《形式语言与自动机理论蒋宗礼第一章参考复习资料[002].docx》由会员分享，可在线阅读，更多相关《形式语言与自动机理论蒋宗礼第一章参考复习资料[002].docx（18页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

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中的元素为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的集合

3、就可以了。 故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 刘秋雯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的子集，那么|

5、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的时候,才同时成立,否那么不成立)(2)

6、 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=2h=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的路，且vn-1,vn

8、存在一条有向边，那么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,b

10、a,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,aa

11、aaabbbba其真前缀集合为：,aa,aaaa,aaaaab,aaaaabbb其后缀集合为：,ba,bbba,abbbba, aaabbbba, aaaaabbbba 其真后缀集合为：,ba,bbba,abbbba, aaabbbba1.25抽象技术为什么对计算机技术特别重要？ 段季芬对于计算机技术方面的人来说，计算思维能力是必需的，这是学科本身决定的。计算机科学及技术学科所要解决的根本问题是什么能被有效的自动化。现代计算机技术认为，要想有效的实现自动化，必须经过抽象进展形式化。126 为什么要求字母表示非空有穷集？ 唐明珠 02282084解答：字母表是非空有穷集合，由字母表中的元素连接而

12、成的字符串叫做字母表上的句子。假设字母表为空集，那么字母表中唯一的元素就是不管如何组合，其组成的句子都为空，其研究就失去了意义，所以字母表要具有非空性。1.27. 考虑一下,为什么要研究句子的前缀,后缀?解: 形式语言是研究自然语言和人工语言的数学工具，只研究组成规那么，不研究语义。而我们将语言看做句子的集合,句子看做字母按照一定规那么组成的字符串,故主要根据规那么的形式区分语言类,大局部问题都可转化为判定某个句子是否属于某个语言的问题.而这就要求从一个句子的构造出发,而一个整体的句子在构造上将其划成几个局部,对于我们的研究会有很大的帮助.事实上研究句子的前缀,后缀,也就是为了将句子构造进展有

13、意识的划分而更加方便的研究句子,看其是否符合某个形式语言的组成规那么.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。解：该语言的每一个句子由

14、三局部构成，这三局部的组成依次为：0、1、0。其中，每局部的0或1的个数不一定相等，但都不小于1个。0n1n0nn0。解：该语言的每一个句子由三局部构成，这三局部的组成依次为：0、1、0。其中，每局部的0或1的个数相等，并且可以都为0。xxTx, 。解：该语言的每一个句子从前向后看和从后向前看时，有一局部是对称相等的。而且，这对称相等的两个串中间一定有另外一个串。x xTx, 。解：该语言的特点是在其句子中一定可以找到这样的一个串：该串是从句子的第一个字符开场的连续的串，且紧跟该串之后的连续一段字符串恰好是该串从后往前看是的那个串，而且这样的两个串之后一定还有另外一个字符串。aaa,。解：该语

15、言的每一个句子有这样的特点：该句子的第一个字符和最后一个字符都是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如果如

16、果，假设那么，而故，原式得证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,. 显然不等。

17、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的真子集，推知后面一项为哪一项前面的一项的真子集，根据吸收规那么所以原式=L10UL1UL

18、12UL13U。=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。*=，L1UL12UL

19、13U。，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+

20、=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 页