资源描述：
《习题及解答教学教材.doc》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、__________________________________________________第3章文法和语言3.8练习（P44）2.文法G[N]为：N→D
2、NDD→0
3、1
4、2
5、3
6、4
7、5
8、6
9、7
10、8
11、9
12、G[N]的语言是什么?=>*>解:NNDn-1=>*.Dn=>*.{0,1,3,4,5,6,7,8,9}+∴L(G[N])={0,1,3,4,5,6,7,8,9}+5.写一文法，使其语言是偶正数的集合。要求：(1)允许0打头(2)不允许0打头解：(1)允许0打头0是正偶数：S→ABB→0
13、2
14、4
15、6
16、8A→AC
17、CC→0
18、1
19、2
20、3
21、4
22、5
23、6
24、7
25、8
26、9
27、ε
28、0不是正偶数：S→FABC
29、FEA→1
30、2
31、3
32、4
33、5
34、6
35、7
36、8
37、9B→BD
38、DD→0
39、1
40、2
41、3
42、4
43、5
44、6
45、7
46、8
47、9
48、εC→0
49、EE→2
50、4
51、6
52、8F→F0
53、ε(2)不允许0打头____________________________________________________________________________________________________S→ABC
54、EA→1
55、2
56、3
57、4
58、5
59、6
60、7
61、8
62、9B→BD
63、DD→0
64、1
65、2
66、3
67、4
68、5
69、6
70、7
71、8
72、9
73、εC→0
74、EE→2
75、4
76、6
77、89.考虑下面上下文无关文法：S→SS*
78、SS+
79、a
80、(1)表明通过此文法如何生成串aa+a*，并为该串构造推导树。(2)该文法生成的语言是什么？解：(1)S=>SS*=>SS+S*=>*.aa+a*该串的推导树如下：S*SSS+Saaa(2)该文法生成的语言是只含+、*的算术表达式的逆波兰表示。11.令文法G[E]为：E→T
81、E+T
82、E-TT→F
83、T*F
84、T/FF→(E)
85、i证明E+T*F是它的一个句型，指出这个句型的所有短语、直接短语和句柄。解：∵E=>E+T=>E+T*F∴E+T*F是文法G[E]的一个句型句型E+T*F的语法树如下：ET+EF*T__________________________________
86、__________________________________________________________________∴E+T*F是句型E+T*F相对于非终结符E的短语T*F是句型E+T*F相对于非终结符T的短语T*F是句型E+T*F相对于规则T→T*F的直接短语T*F是句型E+T*F的句柄13.一个上下文无关文法生成句子abbaa的推导树如下：(1)给出该句子相应的最左推导，最右推导。(2)该文法的产生式集合P可能有哪些元素?(3)找出该句子的所有短语，简单短语、句柄。BSSBABBSεAabbaa解：(1)最左推导如下：S=>ABS=>aBS=>aS
87、BBS=>aBBS=>abBS=>abbS=>abbAa=>abbaa最右推导如下：S=>ABS=>ABAa=>ABaa=>ASBBaa=>ASBbaa=>ASbbaa=>Abbaa=>abbaa(2)该文法的产生式集合P可能有以下元素：S→ABS
88、Aa
89、εB→SBB
90、bA→a(3)为方便叙述将句型abbaa写作a1b1b2a2a3该句子的短语有：a1,ε,b1,b2,a2,b1b2,a2a3,a1b1b2a2a3该句子的直接短语有：a1,ε,b1,b2,a2该句子的句柄为：a116.给出生成下述语言的三型文法：(2){anbm
91、n,m≥1}_____________
92、_______________________________________________________________________________________解：该语言的三型文法为：G[S]：S→aBB→aB
93、CC→bC
94、b或G[S]：S→aS
95、aAB→bA
96、b第4章词法分析4.7练习（P66）1．构造下列正规式相应的DFA：(4)b((ab)*
97、bb)*ab解：先将正规式转换为NFA，转换过程如下：12b((ab)*
98、bb)*ab3=>123(ab)*
99、bbabb4=>a123(ab)*bbbb4=>以下为最终所得的NFA图：a1266bb73bb4
100、5baεε=>____________________________________________________________________________________________________然后，将此NFA转换为DFA：转换关系矩阵如下表：CTaTbT0={1}ΦT1={2,4}T1={2,4}T2={5,6}T3={3}T2={5,6}ΦT4={2,4,7}T3={3}ΦT1={2,4}T4={2,4,7}T2={5,6}T3={3}aT0bbT4=>T1T3T2abbb所得DFA图如下：aT0bbT4=>T1T2bba最后
