(3)当A，B为有穷集合时，A?B?AB。证明：设A?n，B?m（1）当n=0，m=0时，A?B?????0?AB 当n=0，m?0时，A?B???B?0?AB 当n?0，m?0时，A?B?A???0?AB（2）假设m?0，n=k时成立，即A?B?AB?mn?mk当n?k?1时，令A?A'??a?，A'??a???A?B??A'??a???B?A'?B??a??B?A'?B??a??B?mk?m?m(k?1)所以，n?k?1时，A?B?AB同理，当n?0，m=k成立时，m=k+1也成立（3）由归纳原理，当A，B为有穷集合时，A?B?AB成立。
（4）设A，B是有穷集合，则从A到B的映射有B个。证明：设A?n?1，B?m?1（1）当n=1，m=1时，从A到B的映射有BAA?1个，成立A（2）假设n=k时成立，即从A到B的映射有B?mk个A当n?k?1时，设A?A'??a?,A'??a???,A'?k从A到B的映射就是从A'??a?到B的映射，从A'到B的映射个数为B（3）由归纳原理，A，B是有穷集合，则从A到B的映射有B个。
A
?mk个，从?a?到B的映射个数为m个，所以从A'??a?到B的映射的个数为m?mk?mk?1(5)G?(V,E)为一个无向图，则?deg(v)?2E。v?V证明：（1）V?1时，E?0，?deg(v)?2E?0成立。v?V（2）设E=m，假设V?n?1时成立，即?deg(v)?2E?2mv?V当V?n?1时，设V?V'??v0?,V'??v0???,?deg(v)?2E'?2mv?V'
若v0与0?k?n个结点相连，则增加边数k，deg(v0)?k，对于n个结点增加度数也为k，所以，?deg(v)?2E'?2k?（2m?k）=2Ev?V（3）由归纳原理，G?(V,E)为一个无向图，则?deg(v)?2E。v?V
16
(6)G?(V,E)为一个有向图，则?ideg(v)??odeg(v)?E。v?Vv?V证明：（1）V?1时，E?0，?ideg(v)??odeg(v)?0?E成立v?Vv?V（2）设E=m，假设V?n?0时成立，即?ideg(v)??odeg(v)?E成立v?Vv?V当V?n?1时，设V?V'??v0?,V'??v0???，?ideg(v)??odeg(v)?E'?m
v?V'v?V'设ideg(v0)?p，odeg(v0)?q则?ideg(v)??ideg(v)?ideg(v0)??E'?q??p?Ev?Vv?V'v?V?odeg(v)??odeg(v)?odeg(v0)??E'?p??q?Ev?V'v?Vv?V（3）由归纳原理，当G?(V,E)为一个有向图时，?ideg(v)??odeg(v)?E
(7)一个高度为n?1的二元树的根结点到叶子的最大路长是n，该树最多含有2n个叶子证明：（1）高度为2时，最多有21?2个叶子，成立（2）假设高度为n+1时成立，即最多有叶子2n个当高度为n+2时，第n+1层上最多有结点2n个，则第n+2层上最多有叶子为2?2n?2n+1个（3）由归纳原理，高度为n+1的二元树最多含有2n个叶子
(8)根据1.4.3节中的相关定义，对字母表?中的任意字符串a，anam?an?m证明：（1）n=0,m=0时，a0a0??????a0成立（2）假设n=p，m=q时成立，即apaq?ap?q当n=p+1，m=q时，ap+1aq?a?aa?a?a?aaa?a?a?aa?aa??????p?1个q个p个q个p个q个
=ap?qa?ap?q+1同理有，n=p，m=q+1成立（3）由归纳原理，anam?an?m成立。
17
(9)对字母表?中的任意字符串x，x的前缀有x?1个。证明：（1）x=0，即x=?时，x的前缀只有它本身，有x?1?1个，成立（2）假设x=n时成立，即x的前缀有x?1?n?1个。当x=n+1时，设x=x'b,x'的前缀有n+1个。x中含有b的前缀只有一个，所以x的前缀有n+1+1个（3）由归纳原理，对字母表?中的任意字符串x，x的前缀有x?1个。
1．21下列集合中哪些是字母表。
(1 ) {1,2}。
(2 ) {a,b,c,…,z}。 (3 ) ?。
(4) {a,b,a,c}。
(5) {0，1，2，3，…,n,…}。 (6) {a,d,f}?{a,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的所有前缀的集合、后缀的集合、真前缀的集合、真后缀的集合。 （02282015 郭会）
解：
由前缀、后缀、真前缀、真后缀的集合可以有：
其前缀集合为：{ε,aa,aaaa,aaaaab,aaaaabbb,aaaaabbbba} 其真前缀集合为：{ε,aa,aaaa,aaaaab,aaaaabbb}
其后缀集合为：{ε,ba,bbba,abbbba, aaabbbba, aaaaabbbba } 其真后缀集合为：{ε,ba,bbba,abbbba, aaabbbba}
18
1.25抽象技术为什么对计算机技术特别重要？
（段季芬）
对于计算机技术方面的人来说，计算思维能力是必需的，这是学科本身决定的。计算机科学与技术
学科所要解决的根本问题是什么能被有效的自动化。现代计算机技术认为，要想有效的实现自动化， 必须经过抽象进行形式化。
1．26 为什么要求字母表示非空有穷集？ （唐明珠 02282084）
解答：字母表是非空有穷集合，由字母表中的元素连接而成的字符串叫做字母表上的
句子。假设字母表为空集，则字母表中唯一的元素就是?,而?不论如何组合，其组成的句子都为空，其研究就失去了意义，所以字母表要具有非空性。
1.27. 考虑一下,为什么要研究句子的前缀,后缀?
解: 形式语言是研究自然语言和人工语言的数学工具，只研究组成规则，不研究语义。而我们将语言看做句子的集合,句子看做字母按照一定规则组成的字符串,故主要根据规则的形式区分语言类,大部分问题都可转化为判定某个句子是否属于某个语言的问题.而这就要求从一个句子的结构出发,而一个整体的句子在结构上将其划成几个部分,对于我们的研究会有很大的帮助.事实上研究句子的前缀,后缀,也就是为了将句子结构进行有意识的划分而更加方便的研究句子,看其是否符合某个形式语言的组成规则.
28．令∑＝{1, 0}，下列语言在结构上有什么样的特点？（吴贤珺 02282047）
⑴
nn
＝{01│n≥1}。 L1解：该语言的每一个句子由二部分构成，这二部分的组成依次为：0、1。其中，每部分的0或1的个数相等，且都不小于1个。 ⑵
Lnm＝{01│n, m≥1}。 2解：该语言的每一个句子由二部分构成，这二部分的组成依次为：0、1。其中，每部分的0或1的个数不一定相等，但都不小于1个。 ⑶
nnn＝{010│n≥1}。 L3解：该语言的每一个句子由三部分构成，这三部分的组成依次为：0、1、0。其中，每部分的0或1的个数相等，且都不小于1个。 ⑷
L4＝{0n1m0k│n, m, k≥1}。
解：该语言的每一个句子由三部分构成，这三部分的组成依次为：0、1、0。其中，每
部分的0或1的个数不一定相等，但都不小于1个。 ⑸
nnn＝{010│n≥0}。 L5 19
解：该语言的每一个句子由三部分构成，这三部分的组成依次为：0、1、0。其中，每
部分的0或1的个数相等，并且可以都为0。 ⑹
T
L6＝{xωx│x, ω∈??}。
解：该语言的每一个句子从前向后看和从后向前看时，有一部分是对称相等的。而且，
这对称相等的两个串中间一定有另外一个串。 ⑺
T
＝{x xω│x, ω∈?L7?}。
解：该语言的特点是在其句子中一定可以找到这样的一个串：该串是从句子的第一个字符开始的连续的串，且紧跟该串之后的连续一段字符串恰好是该串从后往前看是的那个串，而且这样的两个串之后一定还有另外一个字符串。 ⑻
L8＝{aωa│a∈?,ω∈??}。
解：该语言的每一个句子有这样的特点：该句子的第一个字符和最后一个字符都是0
或都是1，且该句子的长度不小于3。 ⑼
L9＝{ε,0,1,11,01,10,11,000,?}。
解：该语言的句子是所有由0和1构成的串，包括空串ε。 ⑽
L10＝{0,1,00,01,10,11,000,?}。
解：该语言的句子是所有由0和1构成的串，不包括空串ε。
1.29设L1，L2，L3，L4分别是Σ1,Σ2,Σ3,Σ4上的语言，能否说L1，L2，L3，L4都是某个字母表Σ上的语言？如果能，请问这个字母表Σ是怎么样的？
（刘钰 02282083）
答：能 Σ=Σ1∪Σ2∪Σ3∪Σ4
1.30 设L1,L2,L3,L4分别是?1,?2,?3,?4上的语言，证明下面的等式成立。
（1）L1?L2?L2?L1
212设?a?L1（2）L1?L,?a?L或a?L2312?a?L2或a?L1??a?L2?L1,故原式得证
3?(L?L)?(L?L)?L231
23设?a?L1?(L?L)?a?L或a?L或a?L20
??a?L1?(L2?L3)