中山大学2016级编译原理期末试卷A1：正规表达式与NFA转换

"中山大学软件学院2016级《编译原理》期末试卷A1，包含关于正则表达式和自动机构造的问题。" 在这份中山大学软件学院2016级的编译原理期末试卷中，主要考察了两个核心知识点：正则表达式和非确定有限状态自动机（NFA）的构造以及最小化为确定有限状态自动机（DFA）。 1. **正则表达式**： - **问题1** 要求写出两种不同情况的正则表达式： a) 所有由0和1组成的字符串，但不包含连续的0。这个问题的答案是 `(0?1)*0?`，其中 `0?` 表示可能存在的单个0，`(0?1)*` 表示任意数量的0或1，最后的 `0?` 再次确保末尾没有连续的0。 b) 所有表示非负二进制数（无前导零）且能被8整除的字符串。答案是 `0|1(1|0)*000`，首先 `0` 或 `1` 开头，接着是任意数量的1或0，最后必须以 `000` 结束，确保该数能被8整除。 2. **非确定有限状态自动机（NFA）与确定有限状态自动机（DFA）**： - **问题2** 与一个给定的正则表达式 `(a|b)*a(a|b)` 相关，要求： a) 使用Thompson算法构建NFA。Thompson算法是一种将正则表达式转化为NFA的方法，不过具体构建过程未给出，通常会涉及状态的创建和边的连接，根据给定的正则表达式，会形成一个包含开始状态、结束状态以及对a和b两种输入的转移状态。 b) 将构建的NFA转换为具有最小状态数的DFA。这个问题展示了DFA最小化的步骤，例如使用ε-封闭和状态合并。给出了部分ε-封闭和移动的结果，但完整的转换过程并未展示。在实际操作中，需要找到等价状态并进行合并，直到无法再合并为止，以达到最少状态的DFA。 这些题目旨在测试学生对编译原理中正则语言理论的理解，包括正则表达式的构造和自动机理论的应用，这些都是编译器设计的基础。对于NFA到DFA的转换，它涉及到状态转换图的分析和优化，这对于理解编译器如何识别和处理语言模式至关重要。