资源描述：
《习题及解答培训讲学.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、ε0不是正偶数：S→FABC
28、FEA→1
29、2
30、3
31、4
32、5
33、6
34、7
35、8
36、9B→BD
37、
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(1)表明通过此文法如何生成串aa+a*，并为该串构造推导树。(2)该文法生成的语言是什么？解：(1)S=>SS*=>SS+S*=>*.aa+a*该串的推导树如下：S*SSS+Saaa(2)该文法生成的语言是只含+、*的算术表达式的逆波兰表示。11.令文法G[
80、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∴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可能有哪些
86、元素?(3)找出该句子的所有短语，简单短语、句柄。BSSBABBSεAabbaa解：(1)最左推导如下：S=>ABS=>aBS=>aSBBS=>aBBS=>abBS=>abbS=>abbAa=>abbaa最右推导如下：S=>ABS=>ABAa=>ABaa=>ASBBaa=>ASBbaa=>ASbbaa=>Abbaa=>abbaa(2)该文法的产生式集合P可能有以下元素：S→ABS
87、Aa
88、εB→SBB
89、bA→a(3)为方便叙述将句型abbaa写作a1b1b2a2a3该句子的短语有：a1,ε,b1,b2,a2,b1b2,a2a3,a1b1b2a2a3该
90、句子的直接短语有：a1,ε,b1,b2,a2该句子的句柄为：a116.给出生成下述语言的三型文法：(2){anbm
91、n,m≥1}解：该语言的三型文法为：G[S]：S→aBB→aB
92、CC→bC
93、b或G[S]：S→aS
94、aAB→bA
95、b第4章词法分析4.7练习（P66）1．构造下列正规式相应的DFA：(4)b((ab)*
96、bb)*ab解：先将正规式转换为NFA，转换过程如下：12b((ab)*
97、bb)*ab3=>123(ab)*
98、bbabb4=>a123(ab)*bbbb4=>以下为最终所得的NFA图：a1266bb73bb45baεε=>然后，将此N
99、FA转换为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最后，将此DFA化简后如下：ZUSQV0，10110，10110图4.163．将图4.16确定化：解：首先，将此NFA转换为DFA：转换关系矩阵如下表：CTaTbT0={S}T1={V,Q}T2={U,Q}T1={V,Q}T3=
100、{Z,V}T2={U,Q}T2={U,Q}T4={V}T5={Z,Q,U}T3={Z,V}T6={Z}T6={Z}T4={V}T6={Z}ΦT5={Z,Q,U}T3={Z,V}T5={Z,Q,U}T6={Z}T6={Z}T6={Z}所得DFA图如下：T0=>T1T3T2T5T6T4000011110，100，1T4T0=>T1T2T3T400001110，1最后，将此DFA化简后如下：7．给文法G[S]：S→aA
101、bQA→aA
102、bB
103、bB→bD
104、aQQ→aQ
105、bD
106、bD→bB
107、aAE→aB
108、bFF→bD
109、aE
110、b构造相应的最小的DFA。S=>ATQ
111、BDEFabbabbbabaabbaba解：首先，将正规式转换成NFA如下：a然后，将此NFA转换为DFA：转换关系矩阵如
