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

《形式语言与自动机理论-蒋宗礼-第一章参考答案》由会员分享，可在线阅读，更多相关《形式语言与自动机理论-蒋宗礼-第一章参考答案（26页珍藏版）》请在金锄头文库上搜索。

1、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,

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 中的元素为 Ai（i=1,2,3,） ，A i 也是集合，A i 中的元素在 110 之间，并且和为 10。根据集合元素的彼此可区分性，可以计算出 Ai 中元素的最多个数，方法是：把 1 开始的正整数逐个相加，直到等于 10（即 10=1+2+3+4） ，这样，A i 中最多有 4 个元素。原因是：从最小的 1 开始，每次加入新的元素都只依次增加 1，这样相加的和最小，

3、要加到 10，元素个数就最多。求出最大的A i4 后，再求出元素个数为 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 请用命题法给出下列集合 2*2.(1)|0,|43|23(4),5|16,0,49(7)| |1xxzabBLxnNababxx且且 且， ， 且 中 的 个 数 是 1的 个 数 的 两 倍（ 8） ， ， 且 中 的 个 数 是 09， ， 且 中 倒 数 第 十 个 字 符|1,0,|Aii iAix为（ 0） =1.3 给出下列集合的幂集.（02282075 冯蕊）(1)

4、(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 ，30，4 ，0 ，3 ，0 ，2，1，2 ，0，1，0 ，1，2， 0，1，30，1，4，0

5、，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，都有 x B又B 为 A 的子集，对于任何 xB 有，xA由集合相等的定义知，A=B2）如果 A为 B的子集，则|A|=|B|证明：A 为 B 的子集，则对于任何 xA有 xB,存在一个集合 C 使

6、 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| 4|A|=|B|综合（1） ， （2）所述，|A|0,都有 z *,均有 xzL 与 yzL 同时成立或者同时不成立(只有当 z1n|n0的时候 ,才同时

7、成立,否则不成立)(2) x,y0n1m|n0,m=0,都有 z *,均有 xzL 与 yzL 同时成立或者同14时不成立(只有当 z0n1m|n,m0的时候,才同时成立,否则不成立 )(3) x,y0n1m|n,m0, 都有 z *,均有 xzL 与 yzL 同时成立或者同时不成立(无论 z 取何值,都不同时成立 )三个等价类为0 n1m|n0,m00 n1m|n0,m= 0和除此之外的 0,1*上的字符1.18 RL 确定的0，1*的等价分类为：10=x10y|x,y0,1*1 n|n10=0m1n|m-n=0=0n1n|n01=0m1n|m-n=12=0m1n|m-n=2.h=0m1n|

8、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，v 2vn-1,vn 为的一条长度为 k 的路3 有向图中路的长度在有向图中，若两顶点 v1,v2 之间存在一条有向

9、边，则 v1,v2 是的一条长位的路若 v1,v2vn-1 为一条长度为 k-1 的路，且 vn-1,vn 存在一条有向边，则 v1，v 2vn-1,vn 为的一条长度为 k 的路4 n 个集合的乘积S1S2=(a,b)|a S1 且 b S2S1 S2Sn=(d,e)|d S1 S2Sn-1 且 e Sn 155 字母 a 的 n 次幂(1) a0=1;(2) an=an-1a;6 字符串 x 的倒序若 x 为单字符，则 x 的倒序是它本身若 x 的倒序为 y, 若 x 后跟一字符 a, 则 xa 的倒序为 ay;7 字符串 x 的长度若 x 为空串，则|x|=0;若字符串 x 的长度为 k

10、,其 xa 或 ax 的长度为 k+18 自然数0 为自然数，如果 x 为自然数，则 x+1 为自然数1.20.使用归纳法证明下列各题。 (吴玉涵 02282091)11()234(1)111234(1)1()1 =() nkknknnn 证 明 ：（ ） =时 ， 成 立（ 2） 假 设 时 成 立 ， 即当 时 ， 1 0nk（ ）所 以 时 成 立（ 3） 由 归 纳 原 理 ， 对 任 一 N-都 成 立16n2n2n2(2)416422112414kkn kkkk+当 时 ， 。证 明 ：（ 1） 当 =时 ， 成 立（ ） 假 设 时 成 立 ， 即当 时 ，（ ）由 知 ， （

11、）所 以 ， （ ） ， 时 成 立 。（ 3） 由 归 纳 原 理 ， ()m0 n=0k1 ABABABABmnkkaABABa当 ， 为 有 穷 集 合 时 ， 。证 明 ： 设 ，（ 1） 当 ， 时 ，当 ， 时 ，当 ， 时 ，（ 2） 假 设 ， 时 成 立 ， 即当 时 ， 令 ， (1)0m=kk+1mknAB所 以 ， 时 ，同 理 ， 当 ， 成 立 时 ， 也 成 立（ 3） 由 归 纳 原 理 ， 当 ， 为 有 穷 集 合 时 ， 成 立 。1111, AAkAkAnBmnkaABBmaBma（ 4） 设 ， 是 有 穷 集 合 ， 则 从 到 的 映 射 有 B个

12、 。证 明 ： 设 ，（ ） 当 =， 时 ， 从 到 的 映 射 有 个 ， 成 立（ 2） 假 设 时 成 立 ， 即 从 到 的 映 射 有 个当 时 ， 设从 A到 的 映 射 就 是 从 到 的 映 射 ， 从 到 的 映 射 个 数 为 个 ，从 到 的 映 射 个 数 为 个 ， 所 以 从 到 的 映 射 的 个 数 为（ 3） 由 归 纳 原 理 ， ， 是 有 穷 集 合 ， 则 从 A到 的 映 射 有 个 。17000 0(5),)deg()21e()1deg()2,()degvv vvGVEEmnmVnVEvkkknVVV为 一 个 无 向 图 ， 则 。证 明 ：（

13、 ） 时 ， ， 成 立 。（ 2） 设 =， 假 设 时 成 立 ， 即当 时 ， 设若 与 个 结 点 相 连 ， 则 增 加 边 数 ， ， 对 于 个 结 点 增 加度 数 也 为 ， 所 以 ， ()2 2, deg()vEGV（ ） =（ 3） 由 归 纳 原 理 ， 为 一 个 无 向 图 ， 则 。000(6),)deg()e()1e()()deg()e(), dgdeg()vvvvvvVEioEimnioVnV vEmivVVVV 为 一 个 有 向 图 ， 则 。证 明 ：（ ） 时 ， ， 成 立（ 2） 设 =， 假 设 时 成 立 ， 即 成 立当 时 ， 设 ，设 0deg()()()(), deg()e()vv vvpqiivEqpooGVioE VV VV，则（ 3） 由 归 纳 原 理 ， 当 为 一 个 有 向 图 时 ，(7)12n n1nn+1 n一 个 高 度 为 的 二 元 树 的 根 结 点 到 叶 子 的 最 大 路 长 是 ， 该 树 最 多 含 有 2个 叶 子证 明 ：（ ） 高 度 为 2时 ， 最 多 有 个 叶 子 ， 成 立（ ） 假 设 高 度 为 时 成 立 ， 即 最 多 有 叶 子 2个当 高 度 为 时 ， 第 n层 上 最 多 有 结 点 个 ， 则 第 +层 上 最