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

第第 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*|11*0* 2 b|aaa*b*b 3-8构造与正规式a|b aa|bba|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