蒋立源编译原理第三版第三章习题与答案(修改后).pdf

编译原理第三章习题与答案 本资源摘要信息涵盖了编译原理第三章的习题与答案，涵盖了文法、状态转换图、NFA、DFA 等概念。 文法 在习题 3-1 中，要求构造一个右线性文法，使得它与给定的文法等价。解决方案是构造出右线性文法 4AB A f UT U faU|a D fbT|b B fcB|c。这种文法可以生成语言 L={a^n b^m | n,m >= 1}。 状态转换图 在习题 3-2 中，要求根据状态转换图，写出相应的右线性文法，并指出它接受的最短输入串和其他四个输入串。解决方案是构造出右线性文法 G[A]: A -> 0D | 1C | 0B | 1C Ef 0B | 1C。这种文法可以生成语言 L={0^n 1^m | n,m >= 1}。 NFA 在习题 3-4 中，要求将 NFA 确定化和最小化。解决方案是将 NFA M 确定化后，得到 DFA M，状态转换矩阵如答案图 3-4-(1) 之 (a) 所示。然后，将 DFA M 最小化，得到一个状态数最小的 DFA。 DFA 在习题 3-5 中，要求将具有 & 动作的 NFA 确定化。解决方案是将 NFA 确定化后，得到 DFA，状态转换矩阵如答案图 3-5 之所示。 正规式 在习题 3-6 中，要求用正规式描述给定的文法 G[S] 所产生的语言。解决方案是构造出正规式 (a|b) *(aa|bb)(a|b) *，可以生成语言 L={a^n b^m | n,m >= 1}。 状态转换矩阵 在习题 3-3 中，要求画出状态转换图，并写出相应的 3 型文法。解决方案是构造出状态转换图，如答案图 3-3 之所示，并写出相应的 3 型文法，如答案所示。 以上是编译原理第三章习题与答案的摘要信息，涵盖了文法、状态转换图、NFA、DFA 等概念。