资源描述:
《第2章 作业及参考答案》由会员上传分享,免费在线阅读,更多相关内容在行业资料-天天文库。
1、4题:文法G的产生式集合如下,试给出句子aaabbbccc的一个推导和一个归约S→aBC
2、aSBCCB→BCaB→abbB→bbbB→bbC→bccC→ccC→cc6题:文法G的产生式集合如下,请给出G中每个语法范畴代表的集合S→aSa
3、aaSaa
4、aAaA→bA
5、bbbA
6、bBB→cB
7、cCC→ccC
8、DDD→dD
9、d7题:给定如下文法,请用自然语言描述它们定义的语言(4)S→aB
10、bAA→a
11、aS
12、BAAB→b
13、bS
14、ABB8题:设∑={0,1},请给出∑上下列语言的文法(3)所有以11开头,以11结尾的串;(6)所有长度为偶数的串9题:设∑={a
15、,b,c},构造下列语言的文法(2)L2={anbm
16、n,m≥1}(3)L3={anbnan
17、n≥1}(4)L4={anbmak
18、n,m,k≥1}(6)L6={xwxT
19、x,w∈∑+}(7)L7={w
20、w=wT,w∈∑+}补充:对给定RGS→abA
21、baBA→abA
22、abB→baB
23、ba构造等价文法,新文法的产生式形如:A→a,A→aB,A,B∈V,a∈T参考答案4、文法G的产生式集合如下,试给出句子aaabbbccc的一个推导和一个归约S→aBC
24、aSBCCB→BCaB→abbB→bbbB→bbC→bccC→ccC→cc答:SÞaSBCÞaaSBCB
25、CÞaaaBCBCBCÞaaabCBCBCÞaaabBCCBCÞaaabbCCBCÞaaabbCBCCÞaaabbBCCCÞaaabbbCCCÞaaabbbccCÞaaabbbccc6、文法G的产生式集合如下,请给出G中每个语法范畴代表的集合S→aSa
26、aaSaa
27、aAaA→bA
28、bbbA
29、bBB→cB
30、cCC→ccC
31、DDD→dD
32、d解:(注意方法)Set(D)={dm
33、m≥1}set(C)={c2ndm
34、n≥0,m≥2}(注意:d只要大于2,不一定是偶数,可以没有c)set(B)={cndm
35、n≥1,m≥2}set(A)={bkcndm
36、k≥1,n
37、≥1,m≥2}set(S)={apbkcndmap
38、p≥1,k≥1,n≥1,m≥2}问题:不可写作:S={……}讨论:------06级张言飞7(4)、给定如下文法,请用自然语言描述它们定义的语言S→aB
39、bAA→a
40、aS
41、BAAB→b
42、bS
43、ABB解:该文法定义字母表∑={a,b}上的所有a和b的个数相等的字符串构成的语言。分析:若仅考虑产生式S→aB
44、bA,A→a
45、aS,B→b
46、bS,可知文法确定由ab和ba产生的非空串,如abbaba、abbabaab等,加入产生式A→BAA和B→ABB后,可视为在原有A的前面加上BA及在原有B的前面加上AB,这
47、样A、B的出现是成对的,实际上加入这两个产生式的作用就是使连续的多个a和b,如aaabbb成为可能。所以,该文法产生a、b个数相同的非空字符串。或:先改变文法后再分析S→aB
48、bAA→a
49、aS
50、CAB→b
51、bS
52、DBC→BAD→AB-----------06级付海静,黄雪璨付海静8、设∑={0,1},请给出∑上下列语言的文法(3)所有以11开头,以11结尾的串;解:S→11A11,A→ε
53、0A
54、1A或:S→11
55、111
56、11A11,A→ε
57、0A
58、1A或:S→11A,A→11
59、0A
60、1A-----05级李祖玄或:S→11
61、11A,A→11
62、0A
63、1A--
64、---06级周潺潺或:S→11A11,A→AA
65、0
66、1
67、ε------05级王士卫(也行但不好)或:S→11A11,A→BA,B→0
68、1
69、ε------05级刘亮(6)所有长度为偶数的串解:S→0A
70、1A,A→0
71、1
72、0S
73、1S或:S→ASA
74、AA
75、ε,A→0
76、1----05级张士光或:S→SA
77、A,A→00
78、01
79、10
80、11----06级曹守印或:S→ASA
81、ε,A→0
82、1----05级吴利青或:S→00S
83、01S
84、10S
85、11S
86、ε----05级岳宝或:S→0A
87、1A
88、ε,A→0
89、1
90、0B
91、1B,B→0A
92、1A----05级李祖玄9、设∑={a,b
93、,c},构造下列语言的文法(2)L2={anbm
94、n,m≥1}解:S→AB,A→a
95、aA,B→b
96、bB或:S→aS
97、aA,A→b
98、bA或:S→aAb,A→aAB
99、ε,B→b
100、bB
101、ε---05级崔卫华或:S→aAb,A→aA
102、aB
103、ε,B→bB
104、ε---06级李更林或:S→aAb,A→aA
105、Ab
106、ε---06级张力强(很简洁,但忽左忽右,也不好)错了但很有意思的解:S→aS
107、Sb
108、a
109、b(错误原因:L2={anbm
110、n,m≥0且n+m≥2})-----05级于文斐(3)L3={anbnan
111、n≥1}解:由产生L={anbncn
112、n≥1}的文法,有S®a
113、BA
114、aSBAAB®BAaB®abbB®bbbA®baaA®aa(4)L4={anbmak
115、n