编译原理 作业答案

《编译原理 作业答案》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、计算机科学系2010春季学期《编译原理》第一次作业参考答案一、下列正则表达式定义了什么语言（用尽可能简短的自然语言描述）？1.b*(ab*ab*)*所有含有偶数个a的由a和b组成的字符串.2.c*a(a

2、c)*b(a

3、b

4、c)*

5、c*b(b

6、c)*a(a

7、b

8、c)*答案一：所有至少含有1个a和1个b的由a，b和c组成的字符串.答案二：所有含有子序列ab或子序列ba的由a，b和c组成的字符串.说明：答案一要比答案二更好，因为用自然语言描述是为了便于和非专业的人员交流，而非专业人员很可能不知道什么是“子序

9、列”，所以相比较而言，答案一要更“自然”.二、设字母表∑={a,b}，用正则表达式（只使用a，b，e，

10、，*，+，？）描述下列语言：1.不包含子串ab的所有字符串.b*a*2.不包含子串abb的所有字符串.b*(ab?)*3.不包含子序列abb的所有字符串.b*a*b?a*注意：关于子串（substring）和子序列（subsequence）的区别可以参考课本第119页方框中的内容.~(≧▽≦)/~~(≧▽≦)/~~(≧▽≦)/~~(≧▽≦)/~~(≧▽≦)/~~(≧▽≦)/~~(≧▽≦

11、)/~~(≧▽≦)/~《编译原理》第二次作业参考答案一、考虑以下NFA：1.这一NFA接受什么语言（用自然语言描述）？所有只含有字母a和b，并且a出现偶数次或b出现偶数次的字符串.2.构造接受同一语言的DFA.答案一（直接构造通常得到这一答案）：11计算机科学系2010春季学期答案二（由NFA构造DFA得到这一答案）：一、正则语言补运算1.画出一个DFA，该DFA恰好识别所有不含011子串的所有二进制串.1.画出一个DFA，该DFA恰好识别所有不含011子串的所有二进制串.11计算机科学系2010春

12、季学期规律：构造语言L的补语言L’的DFA，可以先构造出接受L的DFA，再把这一DFA的接受状态改为非接受状态，非接受状态改为接受状态，就可以得到识别L’的DFA.说明：在上述两题中的D状态，无论输入什么符号，都不可能再到达接受状态，这样的状态称为“死状态”.在画DFA时，有时为了简明起见，“死状态”及其相应的弧（上图中的绿色部分）也可不画出.1.再证明：对任一正则表达式R，一定存在另一正则表达式R'，使得L(R')是L(R)的补集.证明：根据正则表达式与DFA的等价性，一定存在识别语言L(R)的DF

13、A.设这一DFA为M，则将M的所有接受状态改为非接受状态，所有非接受状态改为接受状态，得到新的DFAM’.易知M’识别语言L(R)的补集.再由正则表达式与DFA的等价性知必存在正则表达式R’，使得L(R’)是L(R)的补集.一、设有一门小小语言仅含z、o、/（斜杠）3个符号，该语言中的一个注释由/o开始、以o/结束，并且注释禁止嵌套.1.请给出单个正则表达式，它仅与一个完整的注释匹配，除此之外不匹配任何其他串.书写正则表达式时，要求仅使用最基本的正则表达式算子（e，

14、，*，+，？）.参考答案一：/o(

15、o*z

16、/)*o+/思路：基本思路是除了最后一个o/，在注释中不能出现o后面紧跟着/的情况；还有需要考虑的是最后一个o/之前也可以出现若干个o.参考答案二（梁晓聪、梁劲、梁伟斌等人提供）：/o/*(z/*

17、o)*o/2.给出识别上述正则表达式所定义语言的确定有限自动机（DFA）.你可根据问题直接构造DFA，不必运用机械的算法从上一小题的正则表达式转换得到DFA.~(≧▽≦)/~~(≧▽≦)/~~(≧▽≦)/~~(≧▽≦)/~~(≧▽≦)/~~(≧▽≦)/~~(≧▽≦)/~~(≧▽≦)/

18、~《编译原理》第三次作业参考答案一、考虑以下DFA的状态迁移表，其中0，1为输入符号，A~H代表状态：0111计算机科学系2010春季学期ABABACCDBDDAEDFFGEGFGHGD其中A为初始状态，D为接受状态，请画出与此DFA等价的最小DFA，并在新的DFA状态中标明它对应的原DFA状态的子集.说明：有些同学没有画出状态H，因为无法从初始状态到达状态H.从实用上讲，这是没有问题的.不过，如果根据算法的步骤执行，最后是应该有状态H的.一、考虑所有含有3个状态（设为p，q，r）的DFA.设只有r是

19、接受状态.至于哪一个状态是初始状态与本问题无关.输入符号只有0和1.这样的DFA总共有729种不同的状态迁移函数，因为对于每一状态和每一输入符号，可能迁移到3个状态中的一个，所以总共有3^6=729种可能.在这729个DFA中，有多少个p和q是不可区分的（indistinguishable）？解释你的答案.解：考虑对于p和q，在输入符号为0时的情况，在这种情况下有5种可能使p和q无法区分：p和q在输入0时同时迁移到r（1种可能），或者p和q在输入0时，都