资源描述：
《蒋立源编译原理 第三版 第三章 习题与答案(修改后).doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、第3章习题 3-1试构造一右线性文法，使得它与如下的文法等价S→ABA→UTU→aU
2、aD→bT
3、bB→cB
4、c并根据所得的右线性文法，构造出相应的状态转换图。3-2对于如题图3-2所示的状态转换图(1)写出相应的右线性文法；(2)指出它接受的最短输入串；(3)任意列出它接受的另外4个输入串；(4)任意列出它拒绝接受的4个输入串。3-3对于如下的状态转换矩阵：(1)分别画出相应的状态转换图；(2)写出相应的3型文法；(3)用自然语言描述它们所识别的输入串的特征。3-4将如下的NFA确定化和最小化：3-5将如题图3-5所示的具有ε动作的NFA确定化。题图3-5具有ε动作的NFA3-6设有文法G
5、[S]：S→aAA→aA
6、bBB→bB
7、cC
8、cC→cC
9、c试用正规式描述它所产生的语言。3-7分别构造与如下正规式相应的NFA。(1)((0*
10、1)(1*0))*(2)b
11、a(aa*b)*b3-8构造与正规式(a
12、b)*(aa
13、bb)(a
14、b)*相应的DFA。第3章习题答案3-1解：根据文法知其产生的语言是:L[G]={ambnci
15、m,n,i≧1}可以构造与原文法等价的右线性文法:S→aAA→aA
16、bBB→bB
17、cC
18、cC→cC
19、c其状态转换图如下:3-2解:(1)其对应的右线性文法是G[A]:A→0DB→0A
20、1CC→0A
21、1F
22、1D→0B
23、1CE→0B
24、1CF→1A
25、0E
26、0(2)最
27、短输入串为011(3)任意接受的四个输入串为：0110,0011,000011,00110(4)任意拒绝接受的输入串为：0111，1011，1100，10013-3解:(1)相应的状态转换图为：(2)相应的3型文法为：(ⅰ)S→aA
28、bSA→aA
29、bB
30、bB→aB
31、bB
32、a
33、b(ⅱ)S→aA
34、bB
35、aA→bA
36、aC
37、a
38、bB→aB
39、bC
40、bC→aC
41、bC
42、a
43、b(ⅲ)S→aA
44、bB
45、bA→aB
46、bA
47、aB→aB
48、bB
49、a
50、b(ⅳ)S→bS
51、aAA→aC
52、bB
53、aB→aB
54、bC
55、bC→aC
56、bC
57、a
58、b(3)用自然语言描述的输入串的特征为：(ⅰ)以任意个(包括0个)b开头，中间有任意个（大于1
59、）a，跟一个b，还可以有一个由a,b组成的任意字符串。(ⅱ)以a打头，中间有任意个（包括0个）b,再跟a,最后由一个a,b所组成的任意串结尾；或者以b打头，中间有任意个（包括0个）a,再跟b,最后由一个a,b所组成的任意串结尾。(ⅲ)以a打头，后跟任意个（包括0个）b，再跟a，最后由一个a,b所组成的任意串结尾；或者以b打头，由一个a,b所组成的任意串结尾。(ⅳ)以任意个（包括0个）b开头,中间跟aa，最后由一个a,b所组成的任意串结尾；或者以任意个（包括0个）b开头，中间跟ab后，再接任意个（包括0个）a，再接b，最后由一个a,b所组成的任意串结尾。3-4解：(1)将NFAM确定化后得DF
60、AM′，其状态转换矩阵如答案图3-4-(1)之(a)所示，给各状态重新命名，即令：[S]=1,[S,A]=2,[A,B]=3,[B]=4且由于3及4的组成中均含有M的终态B，故3和4组成了DFAM′的终态集Z′。于是，所构造之DFAM′的状态转换矩阵和状态转换图如答案图3-4-(1)之(b)及(c)所示。现将DFAM′最小化：(ⅰ)初始分划由两个子集组成，即π0:{1,2},{3,4}(ⅱ)为得到下一分划，考察子集{1,2}。因为{2}b={3}Ì{3,4}但{1}b=Æ故1和2可区分，于是便得到下一分划π1:{1},{2},{3,4}(ⅲ)又因π1≠π0，再考虑{3,4}，因为{3}b={
61、3}Ì{3,4}而{4}b=Æ故3和4可区分，从而又得到π2:{1},{2},{3},{4}此时子集已全部分裂，故最小化的过程宣告结束，M′即为状态数最小的DFA。(2)将NFAM确定化后得DFAM′，其状态转换矩阵如答案图3-4-(2)之(a)所示，给各状态重新命名，即令：[S]=1,[A]=2,[B,C]=3且由于3的组成中含有M的终态C，故3为DFAM′的终态。于是，所构造之DFAM′的状态转换矩阵和状态转换图如答案图3-4-(2)之(b)及(c)所示。现将DFAM′最小化：(ⅰ)初始分划由两个子集组成，即π0:{1,2},{3}(ⅱ)为得到下一分划，考察子集{1,2}。因为{2}b=
62、{2}Ì{1,2}但{1}b=Æ故1和2可区分，于是便得到下一分划π1:{1},{2},{3}此时子集已全部分裂，故最小化的过程宣告结束，M′即为状态数最小的DFA。(3)将NFAM确定化后得DFAM′，其状态转换矩阵如答案图3-4-(3)之(a)所示，给各状态重新命名，即令：[S]=1,[A]=2,[S,B]=3且由于3的组成中含有M的终态B，故3为DFAM′的终态。于是，所构造之DFAM′的状态转换矩阵和
