资源描述：
《第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结尾的串
15、;（6）所有长度为偶数的串9题:设∑={a,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→BCa
25、B→abbB→bbbB→bbC→bccC→ccC→cc答：SÞaSBCÞaaSBCBCÞ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}(注
35、意：d只要大于2，不一定是偶数，可以没有c)set(B)={cndm
36、n≥1,m≥2}set(A)={bkcndm
37、k≥1,n≥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
47、，可知文法确定由ab和ba产生的非空串，如abbaba、abbabaab等，加入产生式A→BAA和B→ABB后，可视为在原有A的前面加上BA及在原有B的前面加上AB，这样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开头,
53、以11结尾的串;解：S→11A11，A→ε
54、0A
55、1A或：S→11
56、111
57、11A11，A→ε
58、0A
59、1A或：S→11A，A→11
60、0A
61、1A-----05级李祖玄或：S→11
62、11A，A→11
63、0A
64、1A-----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→
78、00
79、01
80、10
81、11----06级曹守印或：S→ASA
82、ε，A→0
83、1----05级吴利青或：S→00S
84、01S
85、10S
86、11S
87、ε----05级岳宝或：S→0A
88、1A
89、ε，A→0
90、1
91、0B
92、1B,B→0A
93、1A----05级李祖玄9、设∑={a,b,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级李更
105、林或：S→aAb，A→aA
106、Ab
107、ε---06级张力强（很简洁，但忽左忽右，也不好）错了但很有意思的解：S→aS
108、Sb
109、a
110、b（错误原因：L2={anbm
111、n,m≥0且n+m≥2}）-----05级于文斐（3）L3={anbnan
112、n≥1}解：由产生L={anbncn
113、n≥1}的文法，有S®aBA
114、aSBAAB®BAaB®abbB®bbbA®baaA®aa（4）L4={anbmak
115、n
