编译原理作业答案.docx

《编译原理》第一次作业参考答案下列正则表达式定义了什么语言(用尽可能简短的自然语言描述)?b*(ab*ab*)**a(a|c)*b(a|b|c)*|c*b(b|c)*a(a|b|c)*答案一:所有至少含有1个a和1个b的由a,:所有含有子序列ab或子序列ba的由a,:答案一要比答案二更好,因为用自然语言描述是为了便于和非专业的人员交流,而非专业人员很可能不知道什么是“子序列”,所以相比较而言,答案一要更“自然”.设字母表∑={a,b},用正则表达式(只使用a,b,e,|,*,+,?)描述下列语言:*a**(ab?)**a*b?a*注意:关于子串(substring)和子序列(subsequence)的区别可以参考课本第119页方框中的内容.~\(≧▽≦)/~~\(≧▽≦)/~~\(≧▽≦)/~~\(≧▽≦)/~~\(≧▽≦)/~~\(≧▽≦)/~~\(≧▽≦)/~~\(≧▽≦)/~《编译原理》第二次作业参考答案考虑以下NFA:这一NFA接受什么语言(用自然语言描述)?所有只含有字母a和b,(直接构造通常得到这一答案):答案二(由NFA构造DFA得到这一答案):正则语言补运算画出一个DFA,,:构造语言L的补语言L’的DFA,可以先构造出接受L的DFA,再把这一DFA的接受状态改为非接受状态,非接受状态改为接受状态,就可以得到识别L’:在上述两题中的D状态,无论输入什么符号,都不可能再到达接受状态,这样的状态称为“死状态”.在画DFA时,有时为了简明起见,“死状态”及其相应的弧(上图中的绿色部分):对任一正则表达式R,一定存在另一正则表达式R',使得L(R')是L(R):根据正则表达式与DFA的等价性,一定存在识别语言L(R),则将M的所有接受状态改为非接受状态,所有非接受状态改为接受状态,得到新的DFAM’.易知M’识别语言L(R)’,使得L(R’)是L(R)、o、/(斜杠)3个符号,该语言中的一个注释由/o开始、以o/结束,,它仅与一个完整的注释匹配,,要求仅使用最基本的正则表达式算子(e,|,*,+,?).参考答案一:/o(o*z|/)*o+/思路:基本思路是除了最后一个o/,在注释中不能出现o后面紧跟着/的情况;还有需要考虑的是最后一个o/(梁晓聪、梁劲、梁伟斌等人提供):/o/*(z/*|o)*o/给出识别上述正则表达式所定义语言的确定有限自动机(DFA).你可根据问题直接构造DFA,不必运用机械的算法从上一小题的正则表达式转换得到DFA.~\(≧▽≦)/~~\(≧▽≦)/~~\(≧▽≦)/~~\(≧▽≦)/~~\(≧▽≦)/~~\(≧▽≦)/~~\(≧▽≦)/~~\(≧▽≦)/~《编译原理》第三次作业参考答案考虑以下DFA的状态迁移表,其中0,1为输入符号,A~H代表状态:DBDDAEDFFGEGFGHGD其中A为初始状态,D为接受状态,请画出与此DFA等价的最小DFA,:有些同学没有画出状态H,,,如果根据算法的步骤执行,(设为p,q,r),因为对于每一状态和每一输入符号,可能迁移到3个状态中的一个,所以总共有3^6=,有多少个p和q是不可区分的(indistinguishable)?:考虑对于p和q,在输入符号为0时的情况,在这种情况下有5种可能使p和q无法区分:p和q在输入0时同时迁移到r(1种可能),或者p和q在输入0时,都迁移到p或q(4种可能).类似地,在输入符号为1时,,,总共有3*3=,总共有5*5*