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

《形式语言与自动机课后习题答案部分》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、课后作业讲解付国宏黑龙江大学计算机科学技术学院ghfu@hlju.edu.cn形式语言与自动机理论2021/6/131(C)GuohongFu,CS@HLJU课后作业作业一：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)作业

2、七：pp.191习题2(1)(2)作业八：pp.230习题11(1),12(2)作业九：pp.233习题15作业十：pp.257-258习题1(1),8(1)GHF2021/6/132(C)GuohongFu,CS@HLJU课后作业一pp.39-41：L基本概念习题21---字母表习题22---前/后缀习题23---前/后缀习题28(1)(2)(10)---L的描述GHF2021/6/133(C)GuohongFu,CS@HLJU课后作业一(cont.)pp.40：习题21判断集合是否字母表的依据非空性有穷性可区分性：字母表中

3、的字符两两互不相同整体性或不可分性解答：(1)、(2)和(6)是字母表，其它不是(3)Ø---不满足非空性(4){a,b,a,c}---不满足可区分性(5){0,1,2,…,n,…}---不满足有穷性GHF2021/6/134(C)GuohongFu,CS@HLJU课后作业一(cont.)pp.40：习题22解答前缀：{,a,aa,aaa,aaaa,aaaaa,aaaaab,aaaaabb,aaaaabbb,aaaaabbbb,aaaaabbbba}真前缀：{,a,aa,aaa,aaaa,aaaaa,aaaaab,aaaa

4、abb,aaaaabbb,aaaaabbbb}后缀：{,a,ba,bba,bbba,bbbba,abbbba,aabbbba,aaabbbba,aaaabbbba,aaaaabbbba}真后缀：{,a,ba,bba,bbba,bbbba,abbbba,aabbbba,aaabbbba,aaaabbbba}GHF2021/6/135(C)GuohongFu,CS@HLJU课后作业一(cont.)pp.40：习题23解答前缀：{,aa,aaaa,aaaaab,aaaaabbb,aaaaabbbba}真前缀：{,aa,aaa

5、a,aaaaab,aaaaabbb}后缀：{,ba,bbba,abbbba,aaabbbba,aaaaabbbba}真后缀：{,ba,bbba,abbbba,aaabbbba}注意是任何串的前缀、真前缀、后缀和真后缀；任何串是自身的前缀和后缀，但不是自身的真前缀和真后缀；注意字母表中的字符的整体性。GHF2021/6/136(C)GuohongFu,CS@HLJU课后作业一(cont.)pp.40：习题28(1)(2)(10)(1)L1={0n1n

6、n1}---表示0和1的个数相同，且所有的0位于1之前，长度大于1的0

7、、1串的集合(2)L2={0n1m

8、n,m1}---表示所有的0位于1之前，长度大于1的0、1串的集合(10)L10={0,1,00,01,10,11,000,…}---表示长度大于0的0、1串的集合GHF2021/6/137(C)GuohongFu,CS@HLJU课后作业二pp.83-85---LG习题7(1)---GL习题8(3)---LG习题9(2)---LGGHF2021/6/138(C)GuohongFu,CS@HLJU课后作业二(cont.)pp.84：习题7(1)用自然语言描述下列文法定义的语言G:A

9、aaA

10、aaBBBcc

11、D#ccDbbbD

12、#解题思路观察每个产生式及其组合产生的子语言的特点；根据开始符的产生式将它们并起来就是整个文法产生的语言；解答(1)D产生式：DbbbD

13、#使用DbbbD可产生句型：(bbb)mD(m1);进一步使用D#可得：L(D)={(bbb)m#

14、m0}GHF2021/6/139(C)GuohongFu,CS@HLJU课后作业二(cont.)(2)B产生式：BBcc

15、D#cc用产生式BBcc产生句型：B(cc)n(n1);结合BD#cc产生句型：D#cc;利用(1)中的结

16、果，L(B)={(bbb)m##(cc)n

17、m0，n1}(3)A产生式：AaaA

18、aaB用产生式AaaA产生句型：(aa)kA(k1);结合产生式AaaB产生句型：(aa)kB(k1);利用(1)中的结果，L(A)={(aa)k(bbb)m##(cc)n

19、k1