中山大学编译原理B卷：2题详解，涉及正则表达式与自动机

在《编译原理》期末考试B卷的第1部分，词法分析题目中，考察了两个关于语言模型和自动机构造的问题。第一个问题是关于一个特定的字母表{a}上的语言，该语言的特性是所有串的长度要么是2的倍数，要么是3的倍数，包括空串ε。具体要求如下： 1. **正则表达式** (10分) - 语言的正则表达式可以用 ((aa)|(aaa))* 来表示，其中两个括号内的表达式分别代表长度为2和3的倍数。然而，如果将答案写作((aa)|(aaa))*，可能会因为不符合标准格式而扣分。标准形式可能更倾向于使用星号(*)来表示重复，即(aa)*和(aaa)*。 2. **不确定有限自动机(NFA)** (3分) - 需要设计一个NFA来识别该语言，这通常涉及构造一个状态图，初始状态可以有一个或多个，根据输入'a'的迭代，确保最终状态只接受符合条件的串。错误的构造，如循环弧指向起始状态或状态间的连接错误，会相应扣分。 3. **确定有限自动机(DFA)** (3分) - 从NFA中确定化得到DFA，需要确保没有多余的路径和状态，且每个状态至多只有一个输入箭头，且每个终结状态只对应一种可能的输入。错误地标记了多个箭头或少于6个状态也可能导致扣分。 第二个问题涉及C++语言的整型常量定义，重点在于理解不同进制数的表示方式： - 整型常量以数字序列表示，通常是十进制。如果以0开头，除非后面跟着非零数字，否则会被解释为八进制数（base eight），但0和0X前缀则用于十六进制数（base sixteen）。 - 特别注意的是，八进制中不能包含数字8和9，这是区分十进制和八进制的关键特征。 这些题目着重考察学生对正则表达式、有限状态自动机理论以及编程语言规范的理解，是编译原理课程中的基础内容，旨在测试学生对语言特性和抽象概念的掌握程度。解答这些问题时，不仅需要扎实的理论知识，还需要良好的逻辑思维和绘图技能。