形式语言与自动机第一章作业
需积分: 9 2 浏览量
2015-06-07
17:02:48
上传
评论
收藏 54KB DOC 举报
1.证明：在二元树的第 i 层至多 有（i1）个结点
归纳法：当 i=1，第一层上
只有一个结点，符合
设对于任意 k1，结论成立。要推出当第 k+1 层时结论成立
∵当有第 k+1 层时，第 k 层 有最多个结点即个结点
当第 k 层每个结点都有两个子树时第 k+1 层达到结点的最大值
即
又∵
∴ 在第 k+1 层至多有个结点， 即原结论成立
P20
1.18
（2）
（3）
（4）
1.21
前缀的集合：{aa,aaaa,aaaaab,aaaaabbb,aaaaabbbba}
后缀的集合：{ba,bbba,abbbba,aaabbbba,aaaaabbbba}
真前缀的集合：{aa,aaaa,aaaaab,aaaaabbb}
真后缀的集合：{ba,bbba,abbbba,aaabbbba}
1.22
(1)具有前缀性质
评论0
最新资源