资源描述：
《第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,b,c},构造下列语言的文法
15、（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ÞaaSBCBCÞaaaBCBCBCÞaaabCBCBCÞaaabBCCB
25、CÞ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≥1,m≥2}set(S)={apbkcndmap
37、p≥1,k≥1,n≥1,m≥2}问题：
38、不可写作：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，这样A、B的出现是成对的，实际上加入这两个产生式的作用就是使连续的多个a和b，如aaabbb成为可能。所以，该文法产生a、
47、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-----06级周潺潺或：S→11A11，A→AA
64、0
65、1
66、ε------05级王士卫（也行但不好）或：S→11A11，A→BA，B→0
67、1
68、ε-----
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,c},构造下列语言的文法（2）L2={anbm
93、n,m≥1}解：S→AB，A→a
94、aA，B→b
95、bB或：S→aS
96、aA，A→b
97、bA或：S→aAb，A→aAB
98、ε,B→b
99、bB
100、
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®aBA
113、aSBAAB®BAaB®abbB®bbbA®baaA®aa（4）L4={anbmak
114、n
