蒋立源编译原理第三版习题与答案

第第 3 3 章章习题习题 3-1试构造一右线性文法，使得它与如下的文法等价 S→AB A→UT U→aU|a D→bT|b B→cB|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具有ε动作的 NFA 3-6设有文法 G[S]： S→aAA→aA|bBB→bB|cC|cC→cC|c 试用正规式描述它所产生的语言。 3-7分别构造与如下正规式相应的 NFA。 (1) ((0*|1)(1*0))* (2) b|a(aa*b)*b 3-8构造与正规式(a|b) (aa|bb)(a|b) 相应的 DFA。第第 3 3 章章习题答案习题答案 3-1解：根据文法知其产生的语言是: L[G]={a b c | m,n,i≧1} 可以构造与原文法等价的右线性文法: S→aAA→aA|bBB→bB|cC|cC→cC|c 其状态转换图如下: mni ** 3-2解: (1) 其对应的右线性文法是 G[A]: A →0DB→0A|1CC→0A|1F|1 D→0B|1CE→0B|1CF→1A|0E|0 (2) 最短输入串为 011 (3) 任意接受的四个输入串为： 0110,0011,000011,00110 (4) 任意拒绝接受的输入串为： 0111，1011，1100，1001 3-3解: (1) 相应的状态转换图为： (2) 相应的 3 型文法为： (ⅰ) S→aA|bSA→aA|bB|bB→aB|bB|a|b (ⅱ) S→aA|bB|aA→bA|aC|a|bB→aB|bC|bC→aC|bC|a|b (ⅲ) S→aA|bB|bA→aB|bA|aB→aB|bB|a|b (ⅳ) S→bS|aAA→aC|bB|aB→aB|bC|bC→aC|bC|a|b (3) 用自然语言描述的输入串的特征为： (ⅰ) 以任意个(包括 0 个)b 开头，中间有任意个（大于1）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) 将 NFA M 确定化后得 DFA M′，其状态转换矩阵如答案图 3-4-(1)之(a)所示，给各状态重新命名，即令： [S]=1, [S,A]=2, [A,B]=3, [B]=4 且由于 3 及 4 的组成中均含有 M 的终态 B，故 3 和 4 组成了 DFAM′的终态集 Z′。于是，所构造之 DFA M′的状态转换矩阵和状态转换图如答案图3-4-(1)之(b)及(c)所示。现将 DFA M′最小化： (ⅰ)初始分划由两个子集组成，即 π 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 ={3}{3,4} 而 {4} b = 故 3 和 4 可区分，从而又得到 π 2: {1}, {2}, {3}, {4} 此时子集已全部分裂，故最小化的过程宣告结束，M′即为状态数最小的 DFA。 (2) 将 NFA M 确定化后得 DFA M′，其状态转换矩阵如答案图 3-4-(2)之(a)所示，给各状态重新命名，即令： [S]=1, [A]=2, [B,C]=3 且由于 3 的组成中含有 M 的终态 C，故 3 为 DFA M′的终态。于是，所构造之DFA M′的状态转换矩阵和状态转换图如答案图3-4-(2)之(b)及(c)所示。现将 DFA M′最小化： (ⅰ)初始分划由两个子集组成，即 π 0:{1,2}, {3} (ⅱ)为得到下一分划，考察子集{1,2}。因为 {2} b ={2}{1,2} 但 {1} b = 故 1 和 2 可区分，于是便得到下一分划 π 1: {1}, {2}, {3} 此时子集已全部分裂，故最小化的过程宣告结束，M′即为状态数最小的 DFA。 (3) 将 NFA M 确定化后得 DFA M′，其状态转换矩阵如答案图 3-4-(3)之(a)所示，给各状态重新命名，即令： [S]=1, [A]=2, [S,B]=3 且由于 3 的组成中含有 M 的终态 B，故 3 为 DFA M′的终态。于是，所构造之DFA M′的状态转换矩阵和状态转换图如答案图3-4-(3)之(b)及(c)所示。现将 DFA M′最小化： (ⅰ)初始分划由两个子集组成，即 π 0:{1,2}, {3} (ⅱ)为得到下一分划，考察子集{1,2}。因为 {2} b ={3} 但 {1} b = 故 1 和 2 可区分，于是便得到下一分划 π 1: {1}, {2}, {3} 此时子集已全部分裂，故最小化的过程宣告结束，M′即为状态数最小的 DFA。 (4) 将 NFA M 确定化后得 DFA M′，其状态转换矩阵如答案图 3-4-(4)之(a)所示，给各状态重新命名，即令： [A]=1, [B,C]=2, [B]=3, [C]=4 且由于 2 和 4 的组成中含有 M 的终态 C，故 2 和 4 组成了 DFA M′的终态集 Z′。于是，所构造之 DFA M′的状态转换矩阵和状态转换图如答案图3-4-(4)之(b)及(c)所示。现将 DFA M′最小化： (ⅰ)初始分划由两个子集组成，即 π 0:{1,3}, {2,4} (ⅱ)为得到下一分划，考察子集{1,3}。因为 {1} a ={2}{2,4} 但 {3} a ={1}{1,3} 故 1 和 3 可区分，于是便得到下一分划 π 1: {1}, {3}, {2,4} (ⅲ)又因 π 1≠π0，再考虑{2,4}，因为 {2} a ={4} a ={1}, {2} b ={4} b ={4} 所以 2 和 4 不可区分，故子集{S,B}已不能再分裂。此时π 2