形式语言与自动机课后习题答案部分.ppt

(C)Guohong Fu, CS@HLJU 课后作业讲解 付国宏 黑龙江大学计算机科学技术学院ghfu@hlju.edu.cn 课后作业 作业一：pp.39-41 习题 21, 22, 23, 28(1)(2)(10) 作业二：pp.83-85 习题7(1), 8(3), 9(2) 作业三：pp.126-130 习题 1, 2(3) (5), 7 作业四：pp.128-129 习题 11(1), 15(1) 作业五：pp.129-130 习题 20, 21, 22 作业六：pp.153-155 习题1(5), 2(2), 5(2), 6(图4-24) 作业七：pp.191 习题2 (1) (2) 作业八：pp.230 习题11(1), 12(2) 作业九：pp.233 习题 15 作业十：pp.257-258 习题1(1), 8(1) 课后作业一 pp.39-41：L基本概念 习题 21 ---字母表 习题 22 --- 前/后缀 习题 23 --- 前/后缀 习题 28(1)(2)(10) --- L的描述 课后作业一 (cont.) pp.40：习题 21 判断集合是否字母表的依据 非空性 有穷性 可区分性：字母表中的字符两两互不相同 整体性或不可分性 解答：(1)、(2) 和(6) 是字母表，其它不是 (3)? --- 不满足非空性 (4) {a, b, a, c} --- 不满足可区分性 (5) {0, 1, 2, …, n, …} ---不满足有穷性 课后作业一(cont.) pp.40：习题 22 解答 前缀：{?, a, aa, aaa, aaaa, aaaaa, aaaaab, aaaaabb, aaaaabbb, aaaaabbbb, aaaaabbbba} 真前缀：{?, a, aa, aaa, aaaa, aaaaa, aaaaab, aaaaabb, aaaaabbb, aaaaabbbb} 后缀：{?, a, ba, bba, bbba, bbbba, abbbba, aabbbba, aaabbbba, aaaabbbba, aaaaabbbba} 真后缀：{?, a, ba, bba, bbba, bbbba, abbbba, aabbbba, aaabbbba, aaaabbbba} 课后作业一(cont.) pp.40：习题 23 解答 前缀：{?, aa, aaaa, aaaaab, aaaaabbb, aaaaabbbba} 真前缀：{?, aa, aaaa, aaaaab, aaaaabbb} 后缀：{?, ba, bbba, abbbba, aaabbbba, aaaaabbbba} 真后缀：{?, ba, bbba, abbbba, aaabbbba} 注意 ?是任何串的前缀、真前缀、后缀和真后缀； 任何串是自身的前缀和后缀，但不是自身的真前缀和真后缀； 注意字母表中的字符的整体性。 课后作业一(cont.) pp.40：习题 28(1)(2)(10) (1) L1={0n1n|n?1} --- 表示0和1的个数相同，且所有的0位于1之前，长度大于1的0、1串的集合 (2) L2={0n1m|n, m?1} ---表示所有的0位于1之前，长度大于1的0、1串的集合 (10) L10={0, 1, 00, 01, 10, 11, 000, …} ---表示长度大于0的0、1串的集合 课后作业二 pp.83-85 --- L?G 习题7(1) --- G?L 习题8(3) --- L?G 习题9(2) --- L?G 课后作业二 (cont.) pp.84：习题 7(1) 用自然语言描述下列文法定义的语言 G: A?aaA|aaB B?Bcc|D#cc D?bbbD|# 解题思路 观察每个产生式及其组合产生的子语言的特点； 根据开始符的产生式将它们并起来就是整个文法产生的语言； 解答 (1) D产生式：D?bbbD|# 使用D?bbbD可产生句型：(bbb)mD (m?1); 进一步使用D?#可得：L(D)={(bbb)m#| m?0} 课后作业二 (cont.) (2) B产生式：B?Bcc|D#cc 用产生式B?Bcc产生句型：B(cc)n(n?1); 结合B?D#cc产生句型：D#cc; 利用(1)中的结果， L(B) ={(bbb)m##(cc)n| m?0，n?1} (3) A产生式：A?aaA|aaB 用产生式A?aaA产生句型： (aa)kA(k?1); 结合产生式A?aaB产生句型：(aa)kB(k?1); 利用(1)中的结果， L(A)={(aa)k(bbb)m##